牛客第7场I-Valuable Forests prufer序列+DP

传送门

题意：

定义一个无根树的权值为所有点的度数的平方和，求有标号的n个点形成的所有森林的权值的和。

$T\leq 5000,N \leq 5000$

Solution:

比赛时脑抽，考完五分钟后过了…

由prufer序列的结论可得，对于n个点的无根树，可以形成 $n^{n-2}$ 个不同的树，我们记他的值为 $st_n$ ,那么对于n个点的森林的个数 $f_n$ ，我们可以求得DP式子：

$f(n)=\sum_{i=0}^{n-1}C_{n-1}^if(n-i-1)*st(i+1)$

可以看成将第n个点加入时，选择i个点和他形成一棵树。

接着我们再定义一个n个点能形成的所有无根树的权值和为 $A_n$ ，可以再次推出DP式子：

$A(n)=\sum_{i=1}^n\sum_{d=1}^{n-1}d^2C_{n-2}^{d-1}*(n-1)^{(n-2-d+1)}$

这里我们枚举每一个点i，枚举这个点的度数d，根据prufer序列的性质，第i个点度数为d的贡献可以看成 $d^2$ 与序列中有且仅有d-1个i的方案数之积。

注意到这里i没有用，所以式子可以改为：

$A(n)=n\sum_{d=1}^{n-1}d^2C_{n-2}^{d-1}*(n-1)^{(n-2-d+1)}$ (比赛的时候没有发现…想了半天如何简化)

最后，我们假设n个点的形成的森林的权值和为 $F_n$ ，类似于求 $f_n$ 的方法，我们每次将第n个点加入时，选择i个点和他形成一棵树，这样可以得到DP式子：

$F(n)=\sum_{i=0}^{n-1}C_{N-1}^i*(st(i+1)*F(n-i-1)+f(n-i-1)*A(i+1))$

解释一下后面那坨式子的含义：选择i个点和第n个点形成一个有i+1个点的树，与之相对应，其他的点能形成f(n-i-1)中森林，对于每一种形成方式，都能得到A(i+1)的权值贡献，因此他们需要相乘，前面的式子同理。

这样我们预处理出F(n)，就能O(1)查答案了。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,num[100010];
int a[100010];
int C[5010][5010],A[5010],F[5010],f[5010];
int st[5010];
int T,mod;
int fast_pow(int x,int a)
{
	int ans=1;
	for (;a;x=1ll*x*x%mod,a>>=1)
		if (a&1) ans=1ll*ans*x%mod;
	return ans;
}
int main()
{
	scanf("%d%d",&T,&mod);
	C[0][0]=1;
	for (int i=1;i<=5000;i++)
	{
		C[0][i]=1;
		for (int j=1;j<=i;j++)
			C[j][i]=(1ll*C[j][i-1]+C[j-1][i-1])%mod;
	}
	st[0]=st[1]=1;
	for (int N=1;N<=5000;N++)
	{
		for (int d=1;d<=N-1;d++)
		{
			A[N]=(1ll*d*d*C[d-1][N-2]%mod*fast_pow(N-1,N-2-d+1)+A[N])%mod; 
		}
		A[N]=1ll*N*A[N]%mod;
		if (N>1) st[N]=fast_pow(N,N-2);
	}
	f[0]=1;f[1]=1;
	for (int i=2;i<=5000;i++)
	{
		for (int j=0;j<i;j++)
			f[i]=(1ll*C[j][i-1]*f[i-j-1]%mod*st[j+1]+f[i])%mod;
	}
	for (int N=2;N<=5000;N++)
			for (int i=1;i<=N;i++)
			{
				F[N]=(1ll*C[i-1][N-1]*((1ll*st[i]*F[N-i]%mod+1ll*f[N-i]*A[i]%mod)%mod)+F[N])%mod;
			}
	while (T--)
	{
		scanf("%d",&n);
		
		printf("%d\n",F[n]);
	}
}