YbtOJ 981「prufer编码」森林之和
题目链接：YbtOJ #981
对于一个森林，定义其价值为 图中所有节点度数的平方和。
小 A 想要对所有由 n 个有标号点构成的森林，求出它们的价值之和。(答案向给定的质数 P 取模）
Tle5times10^3，1le nle5times 10^3，2 le P < 2^{30}
Solution
首先看到度数，容易想到 prufer 序列，其有两个重要结论：
- 一棵 n 个点的树和一个长度为 n-2、值域为 1sim n 的整数序列（prufer 序列）一一对应。
- 度数为 d_i 的节点会在 prufer 序列中出现 d_i-1 次。
首先，我们发现每种标号的点对于答案的贡献肯定是一样的，因此我们可以只考虑 1 号点的贡献，然后把这乘个 n 就是答案了。
设 f_n 表示 n 个点的树的个数，根据 prufer 序列的性质可知，因为共有 n^{n-2} 种序列，也就共有 n^{n-2} 种树，即：
然后设 g_n 表示 n 个点的森林个数，有一种对于图的基本递推套路，即枚举 1 号点所在连通块大小 i，得到：
接着考虑设 s_n 表示在所有 n 个点的树中 1 号点度数的平方和，那我们就枚举 1 号点的每种度数 i 去计算相应的方案数。
由于 1 会在 prufer 序列中出现 i-1 次，而剩余的 (n-2)-(i-1)=n-i-1 个位置可以任填 2sim n 中的数，因此递推式就是：
最后设 w_n 表示在所有 n 个点的森林中 1 号点度数的平方和，和 g_n 类似，有递推式：
Code
代码语言：javascript复制#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI) fread(FI,1,FS,stdin),FA==FB)?EOF:*FA )
#define pc(c) (FC==FE&&(clear(),0),*FC =c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3) (x<<1) (oc&15),isdigit(oc=tc()));x*=f;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);}
Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);pc('n');}
}using namespace FastIO;
Cn int N=5e3 10;
int T,p,n,Ans,fac[N],ifac[N],g[N],f[N],s[N];
I int QP(RI a,RI b){if(b<0) return 0;RI s=1;W(b) b&1&&(s=1LL*s*a%p),a=1LL*a*a%p,b>>=1;return s;}
I int C(CI n,CI m){return n<m?0:1LL*fac[n]*ifac[n-m]%p*ifac[m]%p;}
int main(){
freopen("forest.in","r",stdin),freopen("forest.out","w",stdout);
RI i,j,o;read(T,p);for(fac[0]=1,i=1;i<N;i ) fac[i]=1LL*fac[i-1]*i%p;for(ifac[N-1]=QP(fac[N-1],p-2),i=N-2;~i;i--) ifac[i]=1LL*ifac[i 1]*(i 1)%p;
for(f[1]=1,i=2;i<N;i ) f[i]=QP(i,i-2)%p;
for(g[0]=1,i=1;i<N;i ) for(j=1;j<=i;j ) g[i] =1LL*C(i-1,j-1)*g[i-j]%p*f[j]%p,g[i]%=p;
for(i=2;i<N;i ) for(o=1,j=i-1;j;j--) s[i] =1LL*C(i-2,j-1)*o%p*j%p*j%p,s[i]%=p,o=1LL*o*(i-1)%p;W(T--){
for(read(n),Ans=0,i=1;i<=n;i ) Ans =1LL*C(n-1,i-1)*g[n-i]%p*s[i]%p,Ans%=p;
writeln(1LL*Ans*n%p);
}return clear(),0;
}
