題意：一棵$n=2m$個點的樹，$m$個白點和$m$個黑點。對于$k\in [0,n]$，求出 把點黑白兩兩配對使得恰好有$k$對點有祖孫關(guān)系 的方案數(shù) 模$998244353$。

$n\le 5000$

見到恰好考慮容斥（并不

我們欽定$k$對點有祖孫關(guān)系，其他點隨便匹配

這個是個經(jīng)典的樹上背包，設(shè)$f_{u,k}$表示$u$的子樹中欽定$k$對的方案數(shù)

直接把子樹搓起來，然后算上匹配根的方案

看上去是$O(n^3)$，實際上控下上下界可以做到$O(n^2)$

證明是一次的復(fù)雜度是${\sum }_{x,y\in son(u)}si{z}_{x}si{z}_y$，抽象成把所有跨子樹的點對遍歷一次，顯然一個點對只會在lca處被遍歷

算完后記得乘上其它點隨便匹配的方案，即一個階乘

然后二項式反演即可

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #define MAXN 5005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } const int MOD=998244353; inline int add(const int& x,const int& y){return x+y>=MOD? x+y-MOD:x+y;} typedef long long ll; inline int qpow(int a,int p) {int ans=1;while (p){if (p&1) ans=(ll)ans*a%MOD;a=(ll)a*a%MOD;p>>=1;}return ans; } char s[MAXN]; vector<int> e[MAXN]; int col[MAXN],cnt[MAXN][2],lim[MAXN],dp[MAXN][MAXN]; void dfs(int u,int f) {cnt[u][col[u]]=1;dp[u][0]=1; for (int i=0;i<(int)e[u].size();i++)if (e[u][i]!=f){dfs(e[u][i],u);cnt[u][0]+=cnt[e[u][i]][0],cnt[u][1]+=cnt[e[u][i]][1];for (int x=min(cnt[u][0],cnt[u][1]);x>=1;x--)for (int k=max(x-lim[u],1);k<=x&&k<=min(cnt[e[u][i]][0],cnt[e[u][i]][1]);k++)dp[u][x]=(dp[u][x]+(ll)dp[u][x-k]*dp[e[u][i]][k])%MOD;lim[u]=min(cnt[u][0],cnt[u][1]); }for (int x=min(cnt[u][0],cnt[u][1]);x>=0;x--)dp[u][x+1]=(dp[u][x+1]+(ll)(cnt[u][col[u]^1]-x)*dp[u][x])%MOD; } int fac[MAXN],finv[MAXN],ans[MAXN]; inline int C(const int& n,const int& m){return (ll)fac[n]*finv[m]%MOD*finv[n-m]%MOD;} int main() {int n=read();int m=n/2;scanf("%s",s+1);fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(ll)fac[i-1]*i%MOD;finv[n]=qpow(fac[n],MOD-2);for (int i=n-1;i>=0;i--) finv[i]=(ll)finv[i+1]*(i+1)%MOD;for (int i=1;i<=n;i++) col[i]=s[i]-'0';for (int i=1;i<n;i++){int u,v;u=read(),v=read();e[u].push_back(v),e[v].push_back(u);}dfs(1,0);for (int i=0;i<=m;i++) dp[1][i]=(ll)dp[1][i]*fac[m-i]%MOD;for (int i=0;i<=m;i++)for (int j=i;j<=m;j++)ans[i]=add(ans[i],(ll)(((j^i)&1)? (MOD-C(j,i)):C(j,i))*dp[1][j]%MOD);for (int i=0;i<=m;i++) printf("%d\n",ans[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【NOI online 2】游戏【二项式反演】【树上背包】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。