思路
直接正着考虑合法的方案数不是很好做,那么正难则反,可以用总方案数减去不合法方案数,这样容斥一下就能得到答案了。
设 \(F(S)\) 表示集合 \(S\) 中的边不被覆盖的方案数。那么最后的答案就是 \(\displaystyle\sum_{S \subseteq E} (-1)^{|S|}F(S)\)。再思考 \(F(S)\) 怎么求。不难发现一些边不被覆盖相当于把整棵树分成了若干个连通块,根据 \(F\) 的定义,只要求了 \(S\) 中的边不被覆盖,其他边状态随意,因此每个连通块中都可以没有限制的配对。对于一个大小为 \(m\) 的连通块,记 \(sum_m\) 表示它的方案数,若 \(m\) 是奇数,那么任意配对的方案数就是 \(0\),否则对于第 \(1\) 个点,有 \(m-1\) 个点能与其配对,第 \(2\) 个点就要除去 \(1\) 号点配对的两个点,就有 \(m-3\) 个点能与其配对。这样类推下去,\(sum_m\) 便为 \((m-1)\times (m-3)\times\cdots \times 3 \times 1\)。那么 \(F(S)\) 就是每个连通块的方案数乘起来。
快速求解这个 \(F\),于是设 \(f_{u,i}\) 表示以 \(u\) 为根的子树内,\(u\) 所在的连通块大小为 \(i\) 对答案的贡献(不算 \(u\) 的连通块的贡献,带上容斥系数)。转移枚举 \(u\) 的儿子 \(v\) 和他们的连通块大小,分两种:
- \(f_{u,i+j} \gets f_{u,i}\times f_{v,j}\) 表示不把 \(u,v\) 分成两个连通块,而是合并起来。
- \(f_{u,i} \gets f_{u,i} \times f_{v,j} \times (-sum_j)\) 表示把 \(u,v\) 分成两个连通块,这时不被覆盖的边就会增加一条,容斥系数 \(\times (-1)\),同时会让当前的 \(F(S)\) 乘上新增的连通块的方案数 \(sum_j\),故转移时要 \(\times (-sum_j)\)。
最后的答案便是 \(\sum\limits_{i=1}^{n}f_{1,i}\times sum_i\),把自己所在的连通块的贡献乘上(因为状态的定义是不算自己的)。
关于时间复杂度:虽然在转移时要枚举一层 \(sz_u\) 还要枚举一层 \(sz_v\),但是每次都是先转移再累加 \(sz_v\),也就是从 \(v\) 的子树中选点和 \(v\) 旁边的子树选点进行匹配。每一对选出的点都只会在他们的 lca 处被计算一次,故总的复杂度是 \(O(n^2)\)。
code
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=5e3+5,mod=1e9+7;
int n,sz[N];
ll f[N][N],sum[N],tmp[N];
vector<int>e[N];
void dfs(int u,int fa){
sz[u]=1;
f[u][1]=1;
for(auto v:e[u]){
if(v==fa)continue;
dfs(v,u);
for(int i=1;i<=sz[u]+sz[v];++i)tmp[i]=0;
for(int i=1;i<=sz[u];++i){
for(int j=1;j<=sz[v];++j){
tmp[i]=(tmp[i]+mod-f[u][i]*f[v][j]%mod*sum[j]%mod)%mod;
tmp[i+j]=(tmp[i+j]+f[u][i]*f[v][j]%mod)%mod;
}
}
for(int i=1;i<=sz[u]+sz[v];++i)f[u][i]=tmp[i];
sz[u]+=sz[v];
}
}
int main(){
cin>>n;
for(int i=1;i<n;++i){
int a,b;
cin>>a>>b;
e[a].pb(b);
e[b].pb(a);
}
sum[0]=1;
for(int i=2;i<=n;i+=2)sum[i]=sum[i-2]*(i-1)%mod;
dfs(1,0);
ll ans=0;
for(int i=1;i<=n;++i)ans=(ans+f[1][i]*sum[i]%mod)%mod;
cout<<ans;
}
标签:sz,连通,int,配对,sum,Tree,times,ARC101E,Ribbons
From: https://www.cnblogs.com/sunsetlake/p/17989750