简要题面：
求 \(n + d\) 的 \(n\) 正整数拆分中，最大的 \(r\) 个数之和的期望。
首先是典中典：
Key Observation：
最后的形态 \(a_1 \to a_n\) 的概率都是一样的。
Proof：
考虑组合数 \(\binom{d}{a_1 - 1, a_2 - 1 ....., a_n - 1}\)。
然后我们每次在每一个 \(a_i - 1\) 每次分裂有 \((a_i - 1)!\)，然后我们都直接乘上去最后就剩下一个 \(d!\)。
然后发现方案数是一样的。
Solution
这个提示我们直接算所有拆分中最大的 \(r\) 个数的贡献，然后直接除拆分数即可。
考虑把 \(n\) 个 1 减去，直接求整数拆分。
考虑率拆分数形式的 dp。
\(f_{i, j}:\) 前 \(i\) 个数，和为 \(j\)。
\(g_{i, j}:\) 前 \(i\) 个数，和为 \(j\) 的贡献。
那么我们钦定 \(k\) 位有 \(\geq 1\)：
\[f_{i, j} = \sum \binom{i}{k} f_{k, j - k} \]\[g_{i, j} = \sum \binom{i}{k} {g_{k, j - k} + \binom{i}{k}\min(k, r)f_{k, j - k}} \]其中 \(\min(k, r)f_{k, j - k}\) 为直接填上 \(1\) 的贡献。为啥要乘上 \(f_{k, j - k}\)，这个是他出现的次数！
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
/*\yhx12243/ 鱼大保佑*/
using namespace std;
int n, d, r;
long double f[1005][1005], g[1005][1005], c[1005][1005];
int main () {
cin >> n >> d >> r;
c[0][0] = 1;
rep(i, 1, n) c[i][0] = f[i][0] = 1;
rep(i, 1, n) rep(j, 1, i) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
rep(i, 1, n) rep(j, 1, d) {
for (int k = 0; k <= min(i, j); k ++)
f[i][j] += c[i][k] * f[k][j - k];
}
rep(i, 1, n) rep(j, 1, d) {
for (int k = 0; k <= min(i, j); k ++)
g[i][j] += c[i][k] * (g[k][j - k] + min(k, r) * f[k][j - k]);
}
printf("%lf", (double)(g[n][d] / f[n][d] + r));
return 0;
}