题目描述

小A和小B进行一个游戏，在一棵n个点，以1为根的树中，两人各占其中一半的点，每个回合他们会拿出一个之前没用过的点，如果对手的点在自己的点的子树内，则该回合获胜。如果自己的点在对方的子树内，该回合失败。其他情况视为平局。当所有点都被用完时游戏结束。

作为旁观者的你只想知道当他们随机选点的情况下期望有几个回合能决出胜负，即非平局的回合数的期望。

为了计算这个期望，你决定对于k=0~n，计算出恰好有k个回合能决出胜负的方案数，两种方案不同当且仅当存在一个属于小A的点，他被使用的那一个回合小B使用的点不同。答案对998244353取模。

题解

符号没取反+顺序写反=AC

dp部分显然，设f[i][j]表示以i为根连了j对

把f[1][i]乘(m-i)!后二项式反演即可

二项式反演：

来自 https://blog.csdn.net/cold_chair/article/details/81704287

gi其实并不是方案数，至少i的gi意义是把每个大小为i的集合的包含其的集合算一遍的总个数，至多同理

第四条是C(a,b)*C(b,c)=C(a,c)*C(a-c,b-c)，意义是先在a中选c部分，在剩下的选b中剩余部分

第五条是二项式展开

回归本题，求出来的f[1][i]*(m-i)!其实就是g(i)（每个大小为x的算了C(x,i)次），直接反演

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define C(n,m) (jc[n]*Jc[m]%998244353*Jc[(n)-(m)]%998244353)
#define add(a,b) a=((a)+(b))%998244353
#define min(a,b) (a<b?a:b)
#define mod 998244353
#define Mod 998244351
#define ll long long
#define file
using namespace std;

int a[10001][2],ls[5001],sum[5001][2],size[5001],n,m,i,j,k,l,len;
ll f[5001][5001],F[5001],jc[5001],Jc[5001],w[5001],ans[5001],Sum;
bool bz[5001];
char ch;

void New(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}

void dfs(int Fa,int t)
{
	int i,j,k,l;
	size[t]=1;f[t][0]=1;
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa)
	{
		dfs(t,a[i][0]);
		
		sum[t][0]+=sum[a[i][0]][0];
		sum[t][1]+=sum[a[i][0]][1];
		
		memset(F,0,(size[t]+size[a[i][0]]+1)*8);
		fo(j,0,size[t])
		if (f[t][j])
		{
			fo(k,0,size[a[i][0]])
			add(F[j+k],f[t][j]*f[a[i][0]][k]);
		}
		size[t]+=size[a[i][0]];
		memcpy(f[t],F,(size[t]+1)*8);
	}
	++sum[t][bz[t]];
	
	fd(j,sum[t][!bz[t]]-1,0) add(f[t][j+1],f[t][j]*(sum[t][!bz[t]]-j));
}

int main()
{
	freopen("match.in","r",stdin);
	#ifdef file
	freopen("match.out","w",stdout);
	#endif
	
	scanf("%d",&n);m=n/2;
	jc[0]=Jc[0]=jc[1]=Jc[1]=w[1]=1;
	fo(i,1,n)
	{
		ch=getchar();
		while (ch<‘0‘ || ch>‘1‘) ch=getchar();
		bz[i]=ch==‘1‘;
	}
	fo(i,2,n) w[i]=mod-w[mod%i]*(mod/i)%mod,jc[i]=jc[i-1]*i%mod,Jc[i]=Jc[i-1]*w[i]%mod;
	fo(i,1,n-1) scanf("%d%d",&j,&k),New(j,k),New(k,j);
	
	dfs(0,1);
	
	fo(i,0,m) ans[i]=f[1][i]*jc[m-i]%mod;
	fo(i,0,m) {k=-1; fo(j,i+1,m) ans[i]=(ans[i]+ans[j]*C(j,i)*k)%mod,k=-k;}
	fo(i,0,m) printf("%lld ",(ans[i]+mod)%mod);
	printf("\n");
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

6605. 【2020第二场NOI Online能力测试提高组3】游戏(match)（二项式反演）

原文：https://www.cnblogs.com/gmh77/p/12776315.html