Luogu – 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$ 限制的方案数,按照插入的顺序分别考虑。

$$
\underbrace{1\quad2\quad3\quad \cdots\quad i-2\quad i-1\quad i}_{A}\quad\underbrace{ i+1\quad i+2\quad \cdots\quad n-2\quad n-1\quad n}_{B}
$$

$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$ 这条边的贡献,得到答案的表达式:

$$
\operatorname{Ans} = \sum_{i=2}^{n}\sum_{\operatorname{size}_i=1}^{n-i+1} \operatorname{size}_i(n – \operatorname{size}_i) \cdot i!\cdot \binom{n-i}{\operatorname{size}_i-1}(\operatorname{size}_i)! \cdot \frac{(n-\operatorname{size}_i-1)!}{(i-2)!}
$$

把 $i!$ 与 $(i-2)!$ 合并,得到:

$$
\operatorname{Ans} = \sum_{i=2}^{n}\sum_{\operatorname{size}_i=1}^{n-i+1} \operatorname{size}_i(n – \operatorname{size}_i) \cdot \binom{n-i}{\operatorname{size}_i-1}(\operatorname{size}_i)! \cdot {(n-\operatorname{size}_i-1)!}\cdot i(i-1)
$$

预处理阶乘和组合数,$\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;
}

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇