Problem

AtCoder

Solution

发现ARC也有挺多比较有意思的题目……

直接统计是很麻烦的，所以我们不妨考虑容斥。如果有F(S)F(S)F(S)表示SSS集合中的边未被覆盖的答案，那么用一下子集容斥就做完了。

考虑f[x][i]f[x][i]f[x][i]表示x子树内有i个点未匹配的方案数，我们会发现当且仅当i=0i=0i=0时，x的父边是没有被覆盖的，根据子集反演会给我们带来-1的容斥系数，所以不妨在转移时把这个数组当负数来处理，最后输出注意一下即可。其他情况可以O(n2)O(n^2)O(n2)暴力转移。

Code

#include <cstdio>using namespace std;typedef long long ll;const int maxn=5010,mod=1e9+7;template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}template <typename Tp> inline void read(Tp &x){x=0;int f=0;char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') f=1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();if(f) x=-x;}struct data{int v,nxt;}edge[maxn<<1];int n,p,head[maxn],sz[maxn],t[maxn],f[maxn][maxn],g[maxn];inline int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}inline void insert(int u,int v){edge[++p]=(data){v,head[u]};head[u]=p;edge[++p]=(data){u,head[v]};head[v]=p;}void input(){int u,v;read(n);g[0]=1;for(int i=1;i<n;i++){read(u);read(v);insert(u,v);}for(int i=2;i<=n;i+=2) g[i]=(ll)g[i-2]*(i-1)%mod;}void dp(int x,int pre){int v,tot;f[x][sz[x]=1]=1;for(int i=head[x];i;i=edge[i].nxt)if(edge[i].v^pre){v=edge[i].v;dp(v,x);tot=sz[x]+sz[v];for(int j=1;j<=tot;j++) t[j]=0;for(int j=1;j<=sz[x];j++)for(int k=0;k<=sz[v];k++)t[j+k]=pls(t[j+k],(ll)f[x][j]*f[v][k]%mod);for(int j=1;j<=tot;j++) f[x][j]=t[j];sz[x]+=sz[v];}for(int i=1;i<=sz[x];i++) f[x][0]=dec(f[x][0],(ll)f[x][i]*g[i]%mod);}int main(){input();dp(1,1);printf("%d\n",dec(0,f[1][0]));return 0;}