526互联

Codeforces 914H - Ember and Storm's Tree Game（计数）

发布时间 2023-05-03 01:06:36作者: tzc_wk

我这个低能儿怎么这个题调了这么久啊，废了/dk

非常烦的做法，不过也可以看看，代码也不算太难写（

首先注意到很诈骗的一件事情是，只要这个序列 \(a\) 是单峰的或者单谷的（当然，递增递减序列也算在内），都恰有两种方式选择 \((i,op)\) 使得操作完后的序列的单调的，并且显然选树的 Ember 有必胜策略（一条链显然合法），因此我们只用统计满足每个点度数都 \(\le d\)，并且任意两点间的路径都是单峰或单谷的树的数量即可。乘以 \(2n(n-1)\) 就是答案。

考虑两个比较特殊的点：\(1\) 和 \(n\)，显然如果 \(1\) 不是叶子，那么合法的必要条件是当以 \(1\) 为根时每个点的父亲编号都比它小。\(n\) 不是叶子的时候也是类似的。求解这一步考虑 \(dp_{i,j}\) 表示由 \(i\) 个点组成的子树个数，使得根节点儿子个数为 \(j\)，且每个点编号都比其儿子小的方案数，转移考虑将每种 siz 的子树分开来加入，即从小到大枚举 \(i\)，然后枚举大小为 \(i\) 的子树个数 \(j\)。记 \(cnt_i=\sum\limits_{j=0}^{d-1}dp_{i,j}\)，那么容易算得 \(dp_{x,y}\to dp'_{x+ij,y+j}\) 的方案数为 \(cnt_i^j·\dbinom{x+ij}{ij}·\prod\limits_{k=1}^j\dbinom{ki-1}{i-1}\)，预处理后面一大坨即可做到 \(n^3\ln n\)。

这样 \(1,n\) 中有一者不是叶子节点的方案数就能算了——为 \(2f_n-2\)，之所以 \(-2\) 是因为要扣除一条链的情况。接下来考虑 \(1,n\) 都是叶子节点的情况，考虑这条链上的节点——一定是递增的，假设从左到右分别为 \(1=a_0,a_1,a_2,\cdots,a_k,a_{k+1}=n\)，再考虑与链上 \(a_1\sim a_k\) 相连的子树，显然每个子树要么每个点编号都比其父亲大（称之为递增子树），要么每个点编号都比其父亲小（称之为递减子树），而且我们发现，不会出现两个点 \(a_i,a_j(i<j)\) 使得 \(a_i\) 连了一个递增子树，\(a_j\) 连了一个递减子树。只要不存在这样的情况，那么这棵树一定合法。

接下来考虑 DP。分两种情况，不存在一个点既连了递增子树也连了递减子树的情况，和存在一个点既连了递增子树也连了递减子树的情况。这里首先声明一下，我们先假设至少存在一个递增子树和递减子树，因为不存在递增子树和递减子树的情况我们已经在前面算过了。对于前者，考虑 \(f_{i,j}\) 表示链上前 \(i\) 个点连的子树之和为 \(j\) 的方案数，那么容易得到 \(f_{i,j}=\sum\limits_{k=1}^jf_{i-1,j-k}·sdp_{k-1,d-2}·\dbinom{j-1}{k-1}\)，其中 \(sdp_{i,j}=\sum\limits_{k=0}^jdp_{i,k}\)。发现 \(i\) 这一维可以去掉，因此下记 \(f_j=\sum\limits_{i}f_{i,j}\)。然后考虑枚举左右部分的大小，设 \(g_i\) 表示钦定链上最后一个节点的子树大小必须 \(\ge 2\) 的方案数，显然 \(g_i=\sum\limits_{j\le i-2}f_{j}·sdp_{i-j-1,d-2}·\dbinom{i-1}{j}\)，这样我们假设 \(a_i\) 为最靠右的连了递减子树的点，\(a_j\) 为最靠左的连了递增子树的点，我们枚举 \(i\) 左边的 \(siz=x\) 和 \(j\) 右边的 \(siz=y\)，那么显然 \(i\) 左边只能填 \(2\sim x+1\)，\(y\) 右边只能填 \(n-y\sim n-1\)，中间就按顺序填呗，方案数 \(g_i·g_j\)，于是这部分的答案为 \(\sum\limits_{i+j\le n-2}g_ig_j\)。‘

考虑存在一个点既连了递增子树也连了递减子树的方案数。先考虑一个枚举量大一点的算法：枚举这个点左边的子树大小之和 \(x\)，右边的大小之和 \(y\)，连的递增子树的总大小 \(p\)，递减子树的总大小 \(q\)（显然要求 \(x+y+p+q=n-3\)），连的递增子树的个数 \(s\)，连的递减子树的个数 \(t\)（显然要求 \(s+t\le d-2\)），那么方案数是 \(f_xf_y\dbinom{x+p}{x}\dbinom{y+q}{y}dp_{p,s}dp_{q,t}\)，然后发现 \(x,p,s\) 是一组，\(y,q,t\) 是一组，设个 \(h_{i,s}=\sum\limits_{x+p=i}f_x\dbinom{x+p}{x}dp_{p,s}\) 即可做到三方枚举量。

总复杂度 \(O(n^3\ln n)\)，如果模数的 NTT 模数的话可能可以做到 \(n^2\log n\ln n\)，不过没有必要。不知道如果 \(p=998244353\) 数据范围能否开大到 \(10^5\)，反正我是不会，希望比我强的大佬能够给出一个答复。

const int MAXN=200;
int n,d;ll mod,c[MAXN+5][MAXN+5],way[MAXN+5][MAXN+5];
ll dp[MAXN+5][MAXN+5],sdp[MAXN+5][MAXN+5],f[MAXN+5],g[MAXN+5],h[MAXN+5][MAXN+5];
int main(){
	scanf("%d%d%lld",&n,&d,&mod);
	if(d==1&&n>2)return puts("0"),0;
	for(int i=0;i<=n;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	for(int i=1;i<=n;i++){
		way[i][0]=1;
		for(int j=1;j*i<=n;j++)way[i][j]=1ll*way[i][j-1]*c[i*j-1][i-1]%mod;
	}
	dp[0][0]=1;for(int i=0;i<=d;i++)sdp[0][i]=1;
	for(int i=1;i<n;i++){
		static ll tmp[MAXN+5][MAXN+5];
		for(int j=0;j<=n;j++)for(int k=0;k<=d;k++)tmp[j][k]=dp[j][k];
		for(int j=i;j<=n;j++)for(int l=1;l<=d;l++)
			for(int o=1,pw=sdp[i-1][d-1];o*i<=j&&o<=l;o++,pw=1ll*pw*sdp[i-1][d-1]%mod)
				tmp[j][l]=(tmp[j][l]+1ll*dp[j-o*i][l-o]*way[i][o]%mod*c[j][o*i]%mod*pw)%mod;
		for(int j=0;j<=n;j++)for(int k=0;k<=d;k++)dp[j][k]=tmp[j][k];
		for(int l=1;l<=d;l++)sdp[i][l]=(sdp[i][l-1]+dp[i][l])%mod;
	}
	ll res=(2*sdp[n-1][d]+mod-1)%mod;f[0]=1;
	for(int j=1;j<=n-2;j++)for(int k=1;k<=j;k++)
		f[j]=(f[j]+1ll*f[j-k]*sdp[k-1][d-2]%mod*c[j-1][k-1])%mod;
	for(int j=0;j<=n-2;j++)for(int k=2;k+j<=n-2;k++)
		g[k+j]=(g[k+j]+1ll*f[j]*sdp[k-1][d-2]%mod*c[k+j-1][k-1])%mod;
	for(int i=1;i<=n-2;i++)for(int j=1;j<=n-2;j++)
		if(i+j<=n-2)res=(res+1ll*g[i]*g[j])%mod;
	for(int i=0;i<=n-2;i++)for(int j=1;j+i<=n-2;j++)for(int k=1;k<=d-2;k++)
		h[i+j][k]=(h[i+j][k]+1ll*f[i]*c[i+j][i]%mod*dp[j][k])%mod;
	for(int x=1;x<=d-2;x++)for(int y=1;y<=d-2;y++)if(x+y<=d-2)for(int i=1;i<=n-3;i++)
		res=(res+1ll*h[i][x]*h[n-3-i][y])%mod;
	printf("%lld\n",res*n*(n-1)*2%mod);
	return 0;
}