炫酷反演魔术？

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

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;
}