简要题面:
求 \(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\)。
\(f_{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} + \min(k, r)f_{k, j - k}}
\]
其中 \(\min(k, r)f_{k, j - k}\) 为直接填上 \(1\) 的贡献。