记录一些自己做的简单题。

P6478

简单容斥。设 \(f[x][i]\) 表示 \(x\) 为根子树，钦定 \(i\) 对祖孙关系的方案数。

可以用树形背包转移。（顺便给我科普了真正正确的树形背包写法。）

然后可以把根对孩子的贡献加入。

\(f[x][i+1] += f[x][i] \cdot (s-i)\)。

\(s\) 表示子树内与 \(x\) 颜色相反的节点个数。（从剩下的未匹配点中选一个匹配。）

然后恰好的方案数就是 $g[k] = \sum_{i=k}^{m = n/2} (-1)^{i-k} \binom{i}{k}f[1][i] (m-i)!@

这里阶乘表示剩下 \(m-i\) 个点对放任自流。

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
#define ep emplace_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define fin freopen("in.in","r",stdin);
inline int read() {
	int x=0, v=1,ch=getchar();
	while('0'>ch||ch>'9') {
		if(ch=='-') v=0;
		ch=getchar();
	}while('0'<=ch&&ch<='9') {
		x=(x*10)+(ch^'0');
		ch=getchar();
	}return v?x:-x;
}
const int MAX = 5005,P=998244353;
int n, m;
string a;
vector<int>G[MAX];

int fac[2505],inv[2505];
int siz[MAX], s[2][MAX], gg[MAX] , f[MAX][2505]; // 钦定 x 子树内 i 个事件 
void inc(int &x,int y){
	x+=y;if(x>=P)x-=P; 
}
void dfs(int x,int fa) {
	siz[x] = 1, s[a[x]&15][x] = 1;
	f[x][0] = 1;
	for(int y:G[x]) {
		if(y==fa) continue;
		dfs(y, x);
		for(int i=0;i<=min(m,siz[x]+siz[y]);++i) gg[i] = 0;
		for(int i=0;i<=min(m,siz[x]);++i) {
			for(int j=0;j<=min(m,siz[y]);++j) {
				inc(gg[i+j], 1ll * f[x][i] * f[y][j] % P);
			}
		}
		siz[x]+=siz[y];
		for(int i=0;i<=min(m, siz[x]);++i) f[x][i] = gg[i];
		s[0][x]+=s[0][y], s[1][x]+=s[1][y];
	}
	for(int i=min(m, siz[x]+1);i;--i) {
		inc(f[x][i], 1ll * f[x][i-1] * max(0, s[( a[x] & 15 )^ 1][x] - i + 1) % P);
	}	
}
int C(int n,int m){
	return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;
}
int qpow(int x,int p){
	int ret=1;
	for(;p;p>>=1,x=1ll*x*x%P)if(p&1)ret=1ll*ret*x%P;
	return ret;
} 
signed main() { 
	n = read();
	
	m = n >> 1;
	
	fac[0]=1;
	for(int i=1;i<=m;++i)fac[i]=1ll*fac[i-1]*i%P;
	inv[m]=qpow(fac[m],P-2);
	for(int i=m;i>=1;--i)inv[i-1]=1ll*inv[i]*i%P;
	
	cin >> a; a = ' ' + a;
	for(int i=1;i<n;++i) {
		int u,v;
		u = read(),v = read();
		G[u].ep(v), G[v].ep(u);
	}
	dfs(1,0);
	
	
	for(int i=0;i<=m;++i)f[1][i]=1ll*f[1][i]*fac[m-i]%P;
	for(int i=0;i<=m;++i) {
		int ans=0;
		for(int j=i;j<=m;++j){
			inc(ans,1ll * ((j-i&1) ? P-1 : 1) * f[1][j] % P * C(j,i) % P);
		}
		printf("%d\n",ans);
	}
	return 0;
}