自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:25:22，当前版本为作者最后更新于2020-10-31 17:08:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

• 有 $n$ 个人，初始时每个人手上有一颗宝石。
• 在 $d$ 天内，每天会等概率随机一颗宝石，将其分裂为两块宝石。
• 求 $d$ 天后，宝石数前 $r$ 多的人手上宝石数的期望，要求误差不超过 $10^{-6}$。
• $1 \leq n, d \leq 500$，$1 \leq r \leq n$。

题目解法

直接冲上去 dp 怎么看都不是很好做，考虑挖掘一点性质。

先看看对于一种最终状态 $a_1, a_2, \ldots, a_n$，其发生的方案数，我们可以分成两个部分：

第一步是将 $d$ 天分给 $n$ 个人，钦点这 $d$ 天是谁手上的宝石数增加了：

$$\prod_{i=1}^{n}\binom{d-\sum_{j=1}^{i-1}(a_j-1)}{a_i-1}=\frac{d!}{\prod_{i=1}^{n}(a_i-1)!} $$

第二步是对于每一天，计算当天被钦定的人手上宝石数增加的方案数；事实上，在一个人手上的宝石第 $i$ 次增加 $1$ 的时候，这时候发生这种情况的方案数就一定是 $i$ 种。则将 $n$ 个人的方案数都乘起来，则可以认为是：

$$\prod_{i=1}^{n}(a_i-1)!$$

将两个部分乘起来，则我们可以得到一个令人兴奋的结论：对于任何一种最终状态，它发生的方案数都是 $d!$。这也就意味着，所有的最终状态发生的概率都是相等的！

那么我们就可以直接 dp 所有方案数以及这些方案的前 $r$ 大的 $a_i$ 的和就行了。

考虑一种经典的“搭楼梯”的 dp 方法：

我们维护类似这样一个“楼梯”状的东西：

***
******
******
********
********
********
**********
**********

考虑设 $f_{i,j}$ 表示当前最高的“楼梯”有 $i$ 列，“楼梯”里头 * 的总数为 $j$ 的方案数。上面这个东西就是 $f_{3,59}$ 的一种方案。

转移很简单，考虑在最高层加入一行，枚举这行里头有 $k$ 个 *，然后从现有的 $j$ 列里头选 $k$ 列放到最左边，然后在这 $k$ 行上面各加上一个 * 就是一种转移了。比如对上面的 $f_{3,59}$，枚举 $k=2$ 的时候可以转移到 $f_{2,61}$，其转移系数为 $\binom{3}{2}$。转移之后的形态可以这么表示：

**          <--- 新增的行
***
******
******
********
********
********
**********
**********

将这个东西放到这个题中，我们可以将宝石对应成 *，每一列对应一个人就行了。

然后考虑计算所有方案的前 $r$ 大的 $a_i$ 的和。转化成上面的东西就变成了前 $r$ 列的 * 的和。事实上也很简单，由于我们每次加入一行的那些列，一定就是前 $k$ 大的列，而且每列都只加入了一个 *，所以我们可以直接计算贡献。具体来说，我们类比 $f_{i,j}$ 设 $g_{i,j}$ 为当前维护前 $i$ 大，一共有 $j$ 个宝石的所有方案的前 $r$ 大的数的和。那么转移就可以写成：

$$g_{i,j}=\sum_{k=i}^{\min(n,i)}(g_{k,j-i}+\min(i, r) \times f_{k,j-i})\times \binom{k}{i} $$

最后答案也很显然，就是

$$\frac{\sum_{i=1}^{n}g_{i,d}}{\sum_{i=1}^{n}f_{i,d}} $$

了。

由于此题比较神必，所以全上 double 就行了。

Code：(实际写的转移可能和上面叙述的有一点点小区别，本质一样）

typedef long long ll;
typedef double db;

db f[1010][1010];
db g[1010][1010];
db C[1010][1010];

int main() {
	int n = ri, d = ri, r = ri;

	C[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for(int j = 1; j <= i; j++)
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	}

	f[0][n] = 1;
	for(int i = 0; i < d; i++)
		for(int j = 1; j <= n; j++)
			for(int k = 1; k <= j; k++) {
				f[i + k][k] += f[i][j] * C[j][k];
				g[i + k][k] += (g[i][j] + min(r, k) * f[i][j]) * C[j][k];
			}

	db G = 0, F = 0;
	for(int i = 1; i <= n; i++)
		G += g[d][i], F += f[d][i];

	printf("%.8lf\n", G / F + r);

	return 0;
}