[ICPC2018 WF] Gem Island

题面

有 $n$ 个人，最开始每个人手中有 $1$ 颗绿宝石，每天晚上，会随机选一个绿宝石分裂为两个。

求 $d$ 个晚上后绿宝石数量最多的 $r$ 个人的绿宝石数和的期望值。

$1 \le n,d \le 500$ ， $1 \le r\le n$ 。

题解

设最终第 $i$ 个人有 $a_i$ 个宝石，可知其概率

$$\dbinom{d}{a_1 - 1, a_2 - 1, \dots, a_n - 1} \times \dfrac{\prod\limits_{i = 1}^{n}(a_i - 1)}{n^{\overline{d}}} = \dfrac{d!}{n^{\overline{d}}} $$

与具体状态无关，DP。

设 $f_{i,j},g_{i,j}$ 分别表示最大值 $i$ 个，总和 $j$ 的方案数和贡献。

代码

const int N = 1010;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	db f[N][N], g[N][N], C[N][N];
	int n, d, r;
	int main () {
		n = Read(), d = Read(), r = Read();
		C[0][0] = 1;
		for (int i = 1; i <= n; C[i][0] = 1, i++)
			for (int j = 1; j <= i; j++)
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j];

		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;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}