一个显然的结论就是生成树的个数为 $n!$。
Solution1
考虑每条边的贡献，连接的两个连通块大小分别为 $i$ 和 $n-i$，贡献为 $i(n-i)$。
对于第 $i$ 个节点，分别考虑子树内的个数和子树外子树。
子树内
枚举子树大小 $s$。
在 $i$ 子树内的数的大小一定比 $i$ 大，子树大小为 $s$，方案数为 $\dbinom{n-i}{s-1}$。
排列方式有 $s!$，所以总方案数为 $\dbinom{n-i}{s-1}\times s!$。
子树外
枚举子树大小 $s$。
在 $i$ 之前的数的方案为 $i!$。在剩下 $n-i-s+1$ 个数中，一定不能在子树 $i$ 中。所以方案为 $(i-1)\times i\times …\times (n-s-1)$
两者相乘，答案即为：
$$
\sum_{i=2}^n\sum_{s=1}^{n-i+1} s(n-s)\times (n-s-1)!i(i-1)s!\times \dbinom{n-i}{s-1}
$$
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
| #include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 2005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,mod;
int c[maxn][maxn],g[maxn],f[maxn],suf[maxn];
inline void add(int &x,int y) {x=(x+y)%mod;}
signed main(void){
int i,j;
read(n);read(mod);
for (i=0;i<=n;i++) {
c[i][0]=1;
for (j=1;j<=n;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
for (suf[0]=1,i=1;i<=n;i++) suf[i]=suf[i-1]*i%mod;
int ans=0;
for (i=2;i<=n;i++) {
for (j=1;j<=n-i+1;j++) {
add(ans,j*(n-j)%mod*c[n-i][j-1]%mod*suf[j]%mod*i%mod*(i-1)%mod*suf[n-j-1]%mod);
}
}
printf("%lld",ans);
return 0;
}
|
Solution2
另一种想法是考虑两个子树合并。
令 $f_i$ 表示子树大小为 $i$ 时答案，$g_i$ 表示子树到根的距离之和。
不难发现 $f_i$ 的转移依赖于 $g_i$ 。考虑先转移 $g_i$。
$$
g_i=i!(i-1)+\sum\limits_{j=0}^{i-1} (g_i\times (n-i-1)!+g_{n-i-1}\times (i!))\dbinom{i-1}{j}
$$
转移 $f_i$ 可以分为两步。
条件 $1$ 已经被解决。
子树内的贡献 $f_j\times (n-j-1)!+f_{n-j-1}\times j!$
两条边的贡献为 $2\times j\times j!\times (i-j-1)\times (i-j-1)!$
子树之间的贡献为 $g_j\times (n-j-1)!\times (n-j-1)+g_{n-j-1}\times j!\times j$
$$
f_i=g_i+\sum_{j=0}^{i-1}\dbinom{i-1}{j}(f_j\times (n-j-1)!+f_{n-j-1}\times j!+2\times j\times j!\times (i-j-1)\times (i-j-1)!+g_j\times (n-j-1)!\times (n-j-1)+g_{n-j-1}\times j!\times j)
$$
加起来即可。