【洛谷-P4492】[HAOI2018]苹果树

题意#

现在有 $n$ 次操作，每次从当前二叉树上的所有空位（节点的左/右儿子）中等概率选择一个，插入新点。

对最终 $n$ 个点的二叉树，求：两两节点距离之和的期望。

题解#

加入第 $i$ 个点时，方案数为 $i$，根据乘法原理，一共有 $n!$ 种可能的二叉树。只需要计算这些树的权值和。

由于是统计距离之和，考虑按边拆开计算，一条边被经过的次数，能直接算，是这条边两侧的节点个数的乘积。

所以先枚举边。形式化地，枚举 $i\in[2, n]$，则当前边是 $\langle i,\operatorname{father}_i\rangle$，其被经过的次数为 $\operatorname{size}_{i}(n - \operatorname{size}_i)$.

由于 $\operatorname{size}_i$ 并不知道，所以再枚举子树大小 $\operatorname{size}_i\in[1, n-i+1]$.

接下来我们要确定树的形态，求满足 $\operatorname{size}_i$ 限制的方案数，按照插入的顺序分别考虑。

$A$ 段#

包含前 $i$ 个点，这些点和 $i$ 的子树没什么关系，都可以随便插入，共有 $i!$ 种方案。

$B$ 段#

我们首先要从中选出 $\operatorname{size}_i-1$ 个节点插入 $i$ 的子树，共有 $\dbinom{n-i}{\operatorname{size}_i-1}$ 种方案。

这 $\operatorname{size_i}$ 个点是可以以任意顺序组成二叉树的，共有 $(\operatorname{size}_i)!$ 种方案。

对于 $B$ 中剩下的 $n-i-\operatorname{size}_i+1$ 个点，它们都不可以放在 $i$ 的子树内，下面计算这部分的方案数。

上图中，$i=9$，可以发现此时共有 $8=i-1$ 个位置可供选择。

并且，每当我们插入一个节点，可供选择的位置就会增加 $1$。

所以把 $B$ 中剩下的点插入的方案数为：$(i-1)i(i+1)\cdots(n-\operatorname{size}_i-1)=\dfrac{(n-\operatorname{size}_i-1)!}{(i-2)!}$.

把上面的方案数都乘起来，再乘上 $\langle i,\operatorname{father}_i\rangle$ 这条边的贡献，得到答案的表达式：

把 $i!$ 与 $(i-2)!$ 合并，得到：

预处理阶乘和组合数，$\mathcal{O}(n^2)$ 计算即可。

代码#

为了提高可读性，下面代码中统计答案部分的取模操作被省去，直接提交将获得 $\rm{20pts}$ 的好成绩。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e3 + 10;
int N, P;
int fac[MAXN], C[MAXN][MAXN], ans;
signed main() {
	cin >> N >> P;
	fac[0] = 1;
	for(int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % P;
	for(int i = 0; i <= N; i++) C[i][0] = 1;
	for(int i = 1; i <= N; i++) 
        for(int j = 1; j <= i; j++) 
        	C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
	for(int i = 2; i <= N; i++) {
        for(int siz = 1; siz <= N - i + 1; siz++) {
			ans += C[N - i][siz - 1] * siz * (N - siz) * fac[siz] * fac[N - siz - 1] * i * (i - 1);
		}
	}
	cout << ans << endl;
	return 0;
}