NOI Online 游戏树形dp 广义容斥/二项式反演

LINK：游戏

还是过于弱鸡没看出来是个二项式反演,虽然学过一遍但印象不深刻。

二项式反演：有两种形式一种是以恰好和至多的转换一种是恰好和至少得转换。

设\(f_i\)表示至多的方案数 \(g_i\)表示恰好的方案。

则有 \(f_n=\sum_{i=0}^nC(n,i)\cdot g_i\) 根据二项式反演则有 \(g_n=\sum_{i=0}^n(-1)^{n-i}\cdot C(n,i)\cdot f_i\)

设\(f_i\)表示至少的方案数 \(g_i\)表示恰好的方案。

则有 \(f_k=\sum_{i=k}^nC(i,k)\cdot g_i\) 根据二项式反演则有 \(g_k=\sum_{i=k}^n(-1)^{i-k}\cdot C(i,k)\cdot f_i\)

剩下的树形dp还是很容易想的。

题目意思是在所有的局面下不为平局的状态数量。

爆搜复杂度过高。容易发现每次匹配都是在自己和自己的子树内部进行匹配的。

而且匹配是没有顺序的所以对于某种匹配我们直接让其和其子树内部的东西进行匹配即可。

设状态 f[i][j]表示以i为根的子树内部有j个非平局的状态数。

转移很简单不过这里面有一个小trick 注意枚举到自己的子树大小还有不要先加上儿子的数量再枚举这样复杂度都不是n^2的。

只是枚举到自己的子树大小之后可以发现任意两个点对在自己的LCA处被枚举了一遍所以复杂度n^2.

最后有一个自己跟自己匹配的决策转移。

值得一题的是对于有j个非平局的剩下的点还没有被匹配显然方案数为 (m-j)!.

到这里就会发现端倪这个f状态有问题其不是恰好而是至少。

求出所有的f值之后套一个二项式反演就可以得到至少得方案数了。

const ll MAXN=5010,G=3;

ll n,len ;

char a[MAXN];

ll fac[MAXN],inv[MAXN];

ll sz[MAXN][2],w[MAXN],f[MAXN][MAXN];//f[i][j]表示以i为根的子树内至少有j个非平衡的回合数的情况数

ll lin[MAXN],g[MAXN],ver[MAXN<<1],nex[MAXN<<1];

inline void add(ll x,ll y)

{

	ver[++len]=y;

	nex[len]=lin[x];

	lin[x]=len;

}

inline void dfs(ll x,ll fa)

{

	sz[x][a[x]-'0']=1;

	f[x][0]=1;

	go(x)

	{

		if(tn==fa)continue;

		dfs(tn,x);

		ll w1=min(sz[x][1],sz[x][0]);

		ll w2=min(sz[tn][1],sz[tn][0]);

		for(ll j=0;j<=w1;++j)

			for(ll k=0;k<=w2;++k)g[j+k]=(g[j+k]+f[x][j]*f[tn][k])%mod;

		sz[x][1]+=sz[tn][1];

		sz[x][0]+=sz[tn][0];

		rep(0,w1+w2,j)f[x][j]=g[j],g[j]=0;

	}

	ll w1=min(sz[x][0],sz[x][1]);

	fep(w1-1,0,i)f[x][i+1]=(f[x][i+1]+f[x][i]*(sz[x][(a[x]-'0')^1]-i))%mod;

}

inline ll ksm(ll b,ll p)

{

	ll cnt=1;

	while(p)

	{

		if(p&1)cnt=cnt*b%mod;

		b=b*b%mod;p=p>>1;

	}

	return cnt;

}

inline ll C(ll a,ll b){if(a<b)return 0;return fac[a]*inv[b]%mod*inv[a-b]%mod;}

inline void calc()

{

	rep(0,n/2,i)

		rep(i,n/2,j)w[i]=(w[i]+((((j-i)&1))?-1:1)*C(j,i)*g[j])%mod;

}

signed main()

{

	freopen("match.in","r",stdin);

	freopen("match.out","w",stdout);

	gt(n);gc(a);fac[0]=fac[1]=1;

	rep(2,n,i)

	{

		ll get(x),get(y);

		fac[i]=fac[i-1]*i%mod;

		add(x,y);add(y,x);

	}

	inv[n]=ksm(fac[n],mod-2);

	fep(n-1,0,i)inv[i]=inv[i+1]*(i+1)%mod;

	dfs(1,0);

	rep(0,n/2,i)g[i]=f[1][i]*fac[n/2-i]%mod;

	calc();

	//putl(f[1][1]);

	rep(0,n/2,i)printf("%lld ",((w[i]+mod)%mod));

	return 0;

}

巴特西

NOI Online 游戏树形dp 广义容斥/二项式反演

最新文章

热门文章

巴特西

NOI Online 游戏 树形dp 广义容斥/二项式反演

最新文章

热门文章

NOI Online 游戏树形dp 广义容斥/二项式反演