2020牛客暑期多校训练营（第七场）I Valuable Forests

题目大意

我们将无根树T的价值定义为，其中V(T)是T的所有顶点的集合，而d(u)是T的度数。（即内部每个节点度数的平方和）
我们将森林的价值定义为森林中所有树木的价值之和。求所有包含N个节点的森林的价值总和，答案对素数M取模。

解题思路

这题需要用到prufer序列的结论：

初识prufer序列：https://www.cnblogs.com/chenxiaoran666/p/prufer.html

引用文中的证明：
图片说明

因为n个点的无根树可以形成 $n^{n−2}$ 个不同的树，我们设他的值为 $b_n$ ，设n个点的森林个数为 $f_n$ 。在第n个点加入时，我们选择i个点和他形成一棵树，那么就可以列出dp式：

$f_n=\sum_{i=0}^{n-1}C_{n-1}^if(n-i-1)b_{i+1}$

接着我们再定义 $a_n$ 为n个点能形成的所有无根树的价值和。枚举每一个点 $i$ ，再枚举这个点的度数 $j$ 。第 $i$ 个点的度数为 $j$ 的贡献为 $j^2$ 与序列中有且仅有 $j-1$ 个 $i$ 的方案数之积。
所以我们列出下一个式子。因为这里的 $i$ 其实没用，所以这里省去了。

$a_n=\sum_{j=1}^{n-1}C_{n-2}^{j-1}j^2(n-1)^{n-j-1}$

最后，设n个点的形成的森林的价值和（即答案）为 $ans_n$ 。
我们每次加入第n个点，再选择i个点，和它形成一棵树。选择i个点和第n个点，形成一个有i+1个点的树与之相对应，其他的点能形成 $ans(n-i-1)$ 中的森林，对于每一种形成方式，都能得到 $a(i+1)$ 的权值贡献，乘在最后。这样，我们得到最后的式子：

$ans_n=\sum_{i=0}^{n-1}C_{N-1}^i(b_{i+1}ans_{n-i-1}+f_{n-i-1}a_{i+1})$

按照这三个式子，我们最开始顺序预处理过去即可。在代码里能清楚体现出。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int M=100010,N=5010;
int a[N],b[N],c[N][N],f[N],ans[N],mod;
int po(int x,int y)
{
  int z=1;
  while(y)
  {
      if(y&1) z=1ll*z*x%mod;
      x=1ll*x*x%mod,y>>=1;
  }
  return z;
}
int main()
{
  int T,n,i,j;
  scanf("%d%d",&T,&mod);
  b[0]=b[1]=c[0][0]=f[0]=f[1]=1;
  for(i=1;i<=5000;++i)
  {
      c[0][i]=1;
      for(j=1;j<=i;++j)
          c[j][i]=(1ll*c[j][i-1]+c[j-1][i-1])%mod;
  }
  for(i=2;i<=5000;++i)
  {
      for(j=1;j<=i-1;++j)
          a[i]=(1ll*j*j*c[j-1][i-2]%mod*po(i-1,i-2-j+1)+a[i])%mod;
      a[i]=1ll*i*a[i]%mod,b[i]=po(i,i-2);
  }
  for(i=2;i<=5000;++i)
      for(j=0;j<i;++j)
          f[i]=(1ll*c[j][i-1]*f[i-j-1]%mod*b[j+1]+f[i])%mod;
  for(i=2;i<=5000;++i)
      for(j=1;j<=i;++j)
          ans[i]=(1ll*c[j-1][i-1]*((1ll*b[j]*ans[i-j]%mod+1ll*f[i-j]*a[j]%mod)%mod)+ans[i])%mod;
  while(T--) scanf("%d",&n),printf("%d\n",ans[n]);
  return 0;
}