正题
题目大意
一个节点的权值定义为它度数的平方，求所有 n n n个点的有标号森林的所有节点权值和。
1 ≤ n , T ≤ 5 × 1 0 3 1\leq n,T\leq 5\times 10^3 1≤n,T≤5×103
解题思路
首先因为所有节点本质相同，所以我们可以只考虑一个节点所有情况下的权值和。
然后考虑这个平方和怎么做，我们可以视为指定一个节点连出两颗子树的方案（可以相同）。
那么考虑这个怎么做，首先我们需要处理出 n n n个节点有根树和无根树的数组 r , f r,f r,f。
然后我们要考虑怎么统计除了指定子树以外的方案，首先我们需要处理出 n n n个点的森林个数 s n s_n sn。
我们可以考虑每次枚举新加入的树的大小，但是要指定这个节点编号最小的节点编号必须是
1
1
1（以防相同的子树算重），那么有
s
n
=
∑
i
=
1
n
s
n
−
i
f
i
(
n
−
1
i
−
1
)
s_n=\sum_{i=1}^ns_{n-i}f_{i}\binom{n-1}{i-1}
sn=i=1∑nsn−ifi(i−1n−1)
然后还要算上非指定的子树中和
1
1
1号点联通的其他节点的方案，那么有
g
n
=
∑
i
=
0
n
s
i
r
i
+
1
(
n
i
)
g_n=\sum_{i=0}^ns_ir_{i+1}\binom{n}{i}
gn=i=0∑nsiri+1(in)
至于指定子树的话，我们枚举指定子树的大小转移就好了。
时间复杂度： O ( n 2 + T ) O(n^2+T) O(n2+T)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=5100;
ll T,P,C[N][N],f[N],r[N],g[N],s[N],d[N],ans[N];
ll power(ll x,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*x%P;
x=x*x%P;b>>=1;
}
return ans;
}
signed main()
{
freopen("forest.in","r",stdin);
freopen("forest.out","w",stdout);
scanf("%lld%lld",&T,&P);
C[0][0]=1;
for(ll i=1;i<N;i++)
for(ll j=0;j<=i;j++)
C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;
f[0]=f[1]=r[0]=r[1]=g[0]=s[0]=1;
for(ll i=2;i<N;i++)
f[i]=power(i,i-2),r[i]=f[i]*i%P;
for(ll i=1;i<N;i++)
for(ll j=0;j<i;j++)
(s[i]+=s[j]*f[i-j]%P*C[i-1][j]%P)%=P;
for(ll i=1;i<N;i++){
for(ll j=0;j<=i;j++)
(g[i]+=s[j]*f[i-j+1]%P*C[i][j]%P)%=P;
for(ll j=1;j<i;j++)
(ans[i]+=r[j]*g[i-j-1]%P*C[i-1][j]%P)%=P;
}
for(ll i=1;i<N;i++){
d[i]=ans[i+1];
// for(ll j=1;j<=i;j++)
// (d[i]+=r[j]*g[i-j]%P*C[i][j]%P)%=P;
for(ll j=1;j<i-1;j++)
(ans[i]+=d[j]*r[i-j-1]%P*C[i-1][j]%P)%=P;
}
while(T--){
ll n;scanf("%lld",&n);
printf("%lld\n",ans[n]*n%P);
}
return 0;
}