YbtOJ 981「prufer编码」森林之和

(Updated: )
oi
, ,

题目链接：YbtOJ #981

对于一个森林，定义其价值为 图中所有节点度数的平方和。

小 A 想要对所有由 $n$ 个有标号点构成的森林，求出它们的价值之和。(答案向给定的质数 $P$ 取模）

$T\le5\times10^3$，$1\le n\le5\times 10^3$，$2 \le P < 2^{30}$。

Solution

首先看到度数，容易想到 prufer 序列，其有两个重要结论：

  • 一棵 $n$ 个点的树和一个长度为 $n-2$、值域为 $1\sim n$ 的整数序列（prufer 序列）一一对应。
  • 度数为 $d_i$ 的节点会在 prufer 序列中出现 $d_i-1$ 次。

首先，我们发现每种标号的点对于答案的贡献肯定是一样的，因此我们可以只考虑 $1$ 号点的贡献，然后把这乘个 $n$ 就是答案了。

设 $f_n$ 表示 $n$ 个点的树的个数，根据 prufer 序列的性质可知，因为共有 $n^{n-2}$ 种序列，也就共有 $n^{n-2}$ 种树，即：

$$
f_n=n^{n-2}
$$

然后设 $g_n$ 表示 $n$ 个点的森林个数，有一种对于图的基本递推套路，即枚举 $1$ 号点所在连通块大小 $i$，得到：

$$
g_n=\sum_{i=1}^nC_{n-1}^{i-1}g_{n-i}\times f_i
$$

接着考虑设 $s_n$ 表示在所有 $n$ 个点的树中 $1$ 号点度数的平方和，那我们就枚举 $1$ 号点的每种度数 $i$ 去计算相应的方案数。

由于 $1$ 会在 prufer 序列中出现 $i-1$ 次，而剩余的 $(n-2)-(i-1)=n-i-1$ 个位置可以任填 $2\sim n$ 中的数，因此递推式就是：

$$
s_n=\sum_{i=1}^{n-1}C_{n-2}^{i-1}\times (n-1)^{n-1-i}\times i^2
$$

最后设 $w_n$ 表示在所有 $n$ 个点的森林中 $1$ 号点度数的平方和，和 $g_n$ 类似，有递推式：

$$
w_n=\sum_{i=1}^nC_{n-1}^{i-1}g_{n-i}\times s_i
$$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+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;
}