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个点加入时，我们选择i个点和他形成一棵树，那么就可以列出dp式：

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

• 最后，设n个点的形成的森林的价值和（即答案）为。
  我们每次加入第n个点，再选择i个点，和它形成一棵树。选择i个点和第n个点，形成一个有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;
  }