2020牛客暑期多校训练营（第七场） I、Valuable Forests（数论、 Cayley 公式）

题目链接

题面：

题意：
$n$n 个带有标号的点生成的一个无根树组成的森林的权值为 $\sum d_x^2$∑dx2​，其中 $d_x$dx​ 为 $x$x 号节点的度数。

求 $n$n 个带有标号的点生成的所有不相同的无根森林的权值和。

题解：
（1）Cayley 公式
一个含有 $n$n 个节点的完全图的生成树的个数为 $n^{n-2}$nn−2，即 带有标号的 $n$n 个点生成的无根树的个数为 $n^{n-2}$nn−2

$n$n 个标号节点生成一个有 $k$k 棵无根树的森林，使得给定的 $k$k 个点没有两个点属于同一棵树的方案数为 $k\ast n^{n-k-1}$k∗nn−k−1

(2)
设 $f\left(i\right)$f(i) 为 $i$i 个带标号的节点生成的无根树的方案数，那么 $f\left(i\right)=i^{i-2}$f(i)=ii−2

(3)
设 $g\left(i\right)$g(i) 为 $i$i 个带标号的点生成的无根森林的方案数。
考虑有 $j$j 个点与 $i$i 号点成树，其余的点自成森林。
$g\left(i\right)={\sum }_{j=0}^{i-1}{C}_{i-1}^j\ast f(j+1)\ast g(i-j-1)$g(i)=j=0∑i−1​Ci−1j​∗f(j+1)∗g(i−j−1)

特别的 $g\left(0\right)=1$g(0)=1

然后就很容易想到对于一个点枚举这个点的度数和当前点所在无根树的大小，算出一个点的贡献 $ans$ans，最终 $ans\ast n$ans∗n 即为答案。
可是这样的时间复杂度是 $O\left(T{N}^2\right)$O(TN2) 的，还需要继续化简。

（4）
设 $h\left(i\right)$h(i) 为 $i$i 个带标号的点生成的无根树的权值和。

考虑一个点的贡献，我们枚举这个点的度数 $j$j ，从 $i-1$i−1个点中选取 $j$j 个点直接与这个点相连。其余的点挂在这 $j$j 个点上。

由 $n$n 个标号节点生成一个有 $k$k 棵无根树的森林，使得给定的 $k$k 个点没有两个点属于同一棵树的方案数为 $k\ast n^{n-k-1}$k∗nn−k−1。

我们可以将这 $i-1$i−1 个点看作去生成一个有 $j$j 棵无根树的森林，使得选定的 $j$j 个点没有两个点属于同一棵树。那么这部分方案数为 $j\ast (i-1{)}^{i-1-j-1}$j∗(i−1)i−1−j−1。

那么一个点的贡献为 ${\sum }_{j=1}^{i-1}{j}^2\ast C_{i-1}^j\ast j\ast (i-1{)}^{i-1-j-1}$j=1∑i−1​j2∗Ci−1j​∗j∗(i−1)i−1−j−1

那么 $h\left(i\right)=i\ast {\sum }_{j=1}^{i-1}{j}^2\ast C_{i-1}^j\ast j\ast (i-1{)}^{i-1-j-1}$h(i)=i∗j=1∑i−1​j2∗Ci−1j​∗j∗(i−1)i−1−j−1

这里处理的时候 我们可以把 $j=i-1$j=i−1 单独拿出来处理。

（5）
设 $dp\left(i\right)$dp(i) 表示 $i$i 个带标号的点生成的无根森林的权值和。
考虑有 $j$j 个点与 $i$i 号点成树，其余的点自成森林。
那么这个森林是由 $1+j$1+j 个点的包含 $i$i 号点的树和 $i-1-j$i−1−j 个点的森林组成，那这部分的贡献就是 树的贡献乘上森林的方案数+森林的贡献乘上树的方案数 。
即
$dp\left(i\right)={\sum }_{j=0}^{i-1}{C}_{i-1}^j\ast \left(h\right(j+1)\ast g(i-1-j)+dp(i-1-j)\ast f(j+1\left)\right)$dp(i)=j=0∑i−1​Ci−1j​∗(h(j+1)∗g(i−1−j)+dp(i−1−j)∗f(j+1))

特别的 $dp\left(0\right)=0$dp(0)=0

以上预处理时间复杂度 $O\left(N^2\right)$O(N2)，查询时 $O\left(1\right)$O(1) 查询。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
//const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=5002;
const int maxp=400100;
const int maxm=2100;
const int up=200000;

ll c[maxn][maxn],po[maxn][maxn],f[maxn],g[maxn],h[maxn],dp[maxn];
ll mod;

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

void init(void)
{
    c[0][0]=1;
    for(int i=1;i<maxn;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }

    po[0][0]=1;
    for(int i=1;i<maxn;i++)
    {
        po[i][0]=1;
        for(int j=1;j<maxn;j++)
            po[i][j]=po[i][j-1]*i%mod;
    }

    f[0]=f[1]=1;
    for(int i=2;i<maxn;i++)
        f[i]=po[i][i-2];

    g[0]=1;
    for(int i=1;i<maxn;i++)
    {
        for(int j=0;j<i;j++)
            g[i]=(g[i]+c[i-1][j]*f[j+1]%mod*g[i-j-1]%mod)%mod;
    }

    h[0]=h[1]=0;
    for(int i=2;i<maxn;i++)
    {
        for(int j=1;j<i-1;j++)
            h[i]=(h[i]+j*j*c[i-1][j]%mod*j%mod*po[i-1][i-1-j-1]%mod)%mod;
        h[i]=(h[i]+(i-1)*(i-1))%mod;
        h[i]=i*h[i]%mod;
    }

    dp[0]=0;
    for(int i=1;i<maxn;i++)
    {
        for(int j=0;j<i;j++)
            dp[i]=(dp[i]+c[i-1][j]*((h[j+1]*g[i-1-j]+dp[i-1-j]*f[j+1])%mod)%mod)%mod;
    }

}


int main(void)
{
    int tt;
    scanf("%d%lld",&tt,&mod);
    init();
    while(tt--)
    {
        int n;
        scanf("%d",&n);
        printf("%lld\n",dp[n]);
    }
    return 0;
}