I Valuable Forests(计算森林度数平方和)

题意：定义一个森林的代价为内部每个节点度数的平方和.    问所有带标号的 n 个点的森林的代价和.

分析：https://blog.nowcoder.net/n/8058e5c5e22047d289db9dca35569f27?&toCommentId=6701836

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define MP make_pair
const int inf=0x3f3f3f3f;
const int N=5003;
int mod;
ll a[N],b[N],f[N],ans[N],C[N][N];
ll ksm(ll x,ll y){
    ll t=1;
    while(y){
        if(y&1)
            t=(t*x)%mod;
        y>>=1;
        x=(x*x)%mod;
    }
    return t;
}
int main(){
    int T;
    scanf("%d%d",&T,&mod);
    C[0][0]=1;
    for(int i=1;i<N-2;i++){
        C[0][i]=1;
        for(int j=1;j<=i;j++)
            C[j][i]=(C[j][i-1]+C[j-1][i-1])%mod;
    }

    b[0]=b[1]=1;
    for(int i=2;i<N-2;i++){
        for(int j=1;j<=i-1;j++)
            a[i]=(a[i]+1ll*j*j*C[j-1][i-2]%mod*ksm(i-1,i-2-j+1))%mod;
        a[i]=1ll*i*a[i]%mod;
        b[i]=ksm(i,i-2);
    }
    f[0]=f[1]=1;
    for(int i=2;i<N-2;i++)
        for(int j=0;j<i;j++)
            f[i]=(f[i]+f[i-j-1]*C[j][i-1]%mod*b[j+1]%mod)%mod;
    for(int i=2;i<N-2;i++)
        for(int j=1;j<=i;j++)
            ans[i]=(ans[i]+C[j-1][i-1]*(b[j]*ans[i-j]%mod+f[i-j]*a[j]%mod%mod))%mod;

    while(T--){
        int n;
        scanf("%d",&n);
        printf("%lld
",ans[n]);
    }
    return 0;
}