首先有一个结论——二项式反演
用
f
(
n
)
f(n)
f(n) 表示钦定选择了
n
n
n 个的方案数，
g
(
n
)
g(n)
g(n) 表示实际选择了
n
n
n 个数的方案，那么有
f
(
n
)
=
∑
i
=
n
m
(
−
1
)
n
−
i
(
i
n
)
g
(
i
)
f(n)=\sum_{i=n}^m (-1)^{n-i}\binom{i}{n}g(i)
f(n)=i=n∑m(−1)n−i(ni)g(i)
g
(
n
)
=
∑
i
=
n
m
(
−
1
)
n
−
i
(
i
n
)
f
(
i
)
g(n)=\sum_{i=n}^m (-1)^{n-i}\binom{i}{n}f(i)
g(n)=i=n∑m(−1)n−i(ni)f(i)
我们要求的就是
g
(
n
)
g(n)
g(n)，所以问题转化成了求
f
(
n
)
f(n)
f(n)
用
f
u
,
j
f_{u,j}
fu,j 表示以
u
u
u 为根的子树中，有
j
j
j 对点有父子关系
那么我们可以从儿子转移过来，然后这个点还可以成为一个新的父子关系
注意计算出来之后
f
1
,
i
f_{1,i}
f1,i 要乘上
(
n
2
−
i
)
!
(\frac{n}{2}-i)!
(2n−i)!，因为其他没有选的点对应该也要给他一个顺序
复杂度
O
(
n
2
)
\mathcal O(n^2)
O(n2)
#include<iostream>
#include<cstring>
#include<cassert>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<time.h>
#include<algorithm>
#include<climits>
using namespace std;
# define Rep(i,a,b) for(register int i=a;i<=b;i++)
# define _Rep(i,a,b) for(register int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=5005;
const int mod=998244353;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n;
char s[N];
int head[N],cnt;
int f[N][N],g[N];
int fac[N],inv[N];
int siz[N],ixi[N];
struct Edge{
int to,next;
}e[N<<1];
void add(int x,int y){
e[++cnt]=(Edge){y,head[x]},head[x]=cnt;
}
int Qpow(int base,int ind){
int res=1;
while(ind){
if(ind&1)res=1ll*res*base%mod;
base=1ll*base*base%mod;
ind>>=1;
}
return res;
}
int C(int n,int m){
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void dfs(int u,int fa){
siz[u]=1,ixi[u]=s[u]-'0';
f[u][0]=1;
RepG(i,u){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
Rep(j,0,siz[u]+siz[v])g[j]=0;
Rep(j,0,siz[u])
Rep(k,0,siz[v])
g[j+k]=(g[j+k]+1ll*f[u][j]*f[v][k]%mod)%mod;
Rep(j,0,siz[u]+siz[v])f[u][j]=g[j];
siz[u]+=siz[v];
ixi[u]+=ixi[v];
}
if(s[u]-'0')
_Rep(j,min(ixi[u],siz[u]-ixi[u]),1)
f[u][j]=(f[u][j]+1ll*f[u][j-1]*(siz[u]-ixi[u]-(j-1))%mod)%mod;
else
_Rep(j,min(ixi[u],siz[u]-ixi[u]),1)
f[u][j]=(f[u][j]+1ll*f[u][j-1]*(ixi[u]-(j-1))%mod)%mod;
}
int main()
{
memset(head,-1,sizeof(head));
read(n);
scanf("%s",s+1);
Rep(i,1,n-1){
int x,y;
read(x),read(y);
add(x,y),add(y,x);
}
dfs(1,0);
fac[0]=inv[0]=1;
Rep(i,1,n)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=Qpow(fac[n],mod-2);
_Rep(i,n-1,1)inv[i]=1ll*inv[i+1]*(i+1)%mod;
Rep(i,0,n/2)g[i]=0;
Rep(i,0,n/2)f[1][i]=1ll*f[1][i]*fac[n/2-i]%mod;
Rep(i,0,n/2)
Rep(j,i,n/2)
if((j-i)&1)g[i]=(g[i]-1ll*C(j,i)*f[1][j]%mod+mod)%mod;
else g[i]=(g[i]+1ll*C(j,i)*f[1][j]%mod)%mod;
Rep(i,0,n/2)
printf("%d\n",g[i]);
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
