CF1707D Partial Virtual Tree

CF1707D Partial Virtual Trees

Description

https://www.luogu.com.cn/problem/CF1707D

Solution

学到容斥了，感觉妙妙。

感觉这个 $S_i\not = S_{i+1}$ 很烦，考虑容斥，令 $g_i$ 表示答案序列，$f_i$ 表示不考虑 $S_i\not = S_{i+1}$ 的限制，结尾为 ${1}$，且满足题目限制的方案数。

有 $f_i=\sum\limits_{j\le i} \dbinom{i}{j} g_j$，根据二项式反演，有 $g_i=\sum\limits_{j\le i} (-1)^{i-j}\dbinom{i}{j}f_i$ 。只需要求出 $f$ 即可。

令 $f_{i,j}$ 表示时刻 $j$ 在 $i$ 的子树中仍然有点被选中的方案数。如果一个点有至少两个互不相同的子树中存在被选中的点，那么这个点一定要被选中。否则随便。

分两种情况考虑：

• $i$ 在集合中

  则子树的内可以任意选。
  $$
  f_{i,j}=\prod\limits_{y\in son_i} \sum\limits_{k\le j} f_{y,j}
  $$
  令 $s_{y,j}=\sum\limits_{k\le j} f_{y,k}$，前缀和优化一下是简单的。

• $i$ 不在集合中

  则枚举 $i$ 在 $p$ 到 $p+1$ 的时间熄灭。
  $$
  f_{i,j}=\sum_{p<j}\sum_{x\in son_i} f_{x,j}\prod_{y\in son_i,y\not = x} s_{y,p}
  $$
  预处理一些东西，前后缀积什么的，可以做到全局 $O(n^2)$。

注意最后一个集合一定为 ${1}$。需要特判一下。

Code

#define int long long
#define maxn 2005
int mod;
int c[maxn][maxn];
int n,dp[maxn][maxn],s[maxn][maxn],fs[maxn][maxn],fp[maxn][maxn],ft[maxn],g[maxn],o[maxn];
vector<int>to[maxn];
void add(int &x,int y) {x=(x+y)%mod;}
const int id=1; 
void solve(int x,int pre) {
	int i,j,y;
	for (auto y:to[x]) if (y^pre) solve(y,x);
	for (j=0;j<=n;j++) dp[x][j]=1;
	if (x!=id) {
		int nums=to[x].size(),tot=-1;
		for (i=0;i<nums;i++) 
			if ((y=to[x][i])^pre) {
				o[y]=++tot;
				for (j=1;j<=n;j++) dp[x][j]=dp[x][j]*s[y][j]%mod;
				for (j=0;j<=n;j++) {
					if (tot>0) fs[tot][j]=fs[tot-1][j]*s[y][j]%mod;
					else fs[tot][j]=s[y][j];
				}
			}
		for (i=nums-1;i>=0;i--) if ((y=to[x][i])^pre) {
			for (j=0;j<=n;j++) 
				if (o[y]<tot) fp[o[y]][j]=fp[o[y]+1][j]*s[y][j]%mod;
				else fp[o[y]][j]=s[y][j]; 
		}
		
		for (auto y:to[x]) if (y^pre) {
			for (j=0;j<=n;j++) ft[j]=(o[y]?fs[o[y]-1][j]:1)*(o[y]<tot?fp[o[y]+1][j]:1)%mod;
			for (j=1;j<=n;j++) add(ft[j],ft[j-1]),add(dp[x][j],dp[y][j]*ft[j-1]);
		}
	}
	else {
		for (auto y:to[x]) if (y^pre) {
			for (j=1;j<=n;j++) dp[x][j]=dp[x][j]*s[y][j-1]%mod;
		}
	}
	s[x][0]=1;
	for (j=1;j<=n;j++) add(s[x][j],s[x][j-1]+dp[x][j]);
}
signed main(void){
//	freopen("1.in","r",stdin);
	int i,j,x,y;
	read(n);read(mod);
	for (i=0;i<=n;i++) {
		c[i][0]=1;
		for (j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	for (i=1;i<=n;i++) dp[i][0]=1;
	for (i=1;i<n;i++) {
		read(x),read(y);
		to[x].push_back(y);
		to[y].push_back(x);
	}
	solve(1,0);
	for (i=1;i<n;i++)
		for (j=1;j<=i;j++) {
			int sum=c[i][j]*dp[id][j]%mod;
			if ((i-j)%2==0) add(g[i],sum);
			else add(g[i],mod-sum);
		}
	for (i=1;i<n;i++) printf("%lld ",g[i]);
	return 0;
}