有一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$，初始时所有的 $a_i$ 都等于 $1$。现在要对这个序列进行 $d$ 次操作，每次操作如下：
设 $d$ 次操作后的序列从大到小排序后为 $b_1 \geq b_2 \geq \cdots \geq b_n$，对于固定的 $r \in \left[ 1, n \right]$，求 $b_1 + b_2 + \cdots + b_r$ 的期望。
共一行，包含三个正整数 $n, d, r$ ($1 \leq n, d \leq 500; 1 \leq r \leq n$)，分别表示序列的长度，操作的次数和最终求前 $r$ 大值的期望。
输出一行一个实数，表示 $d$ 次操作后 $b_1 + b_2 + \cdots + b_r$ 的期望。答案被认为正确当且仅当相对或绝对误差不超过 $10^{-6}$。
设 $d$ 次操作后的序列 (未排序) 为 $A_1, A_2, \cdots, A_n$，显然有 $A_1 + A_2 + \cdots + A_n = n + d$。
任取满足 $x_1 + x_2 + \cdots + x_n = n + d$ 的正整数序列 $\left\{ x_n \right\}$，那么序列 $\left\{ A_n \right\}$ 有一定概率与 $\left\{ x_n \right\}$ 完全相同。
由小学数学可知，满足 $x_1 + x_2 + \cdots + x_n = n + d$ 的正整数序列的个数恰好为 $\dbinom {d + n - 1} {n - 1}$。
考虑计算序列 $\forall i \in \left[ 1, n \right], A_i = x_i$ 的概率。经过适当地打表找规律发现，所有 $\dbinom {d + n - 1} {n - 1}$ 个 $\left\{ x_n \right\}$ 作为最终序列 $\left\{ A_n \right\}$ 的概率都是相同的，都等于 $\dfrac 1 {\dbinom {d + n - 1} {n - 1}}$。
对于序列从 $\left[ 1, 1, \cdots, 1 \right]$ 变成 $\left[ x_1, x_2, \cdots, x_n \right]$，可知第 $i$ 个数被执行 $+ 1$ 操作 $x_i - 1$ 次。
因此由多项式系数可知不同的操作序列一共有 $\dbinom d {x_1 - 1, x_2 - 1, \cdots, x_n - 1}$ 种。
对于每种操作序列，它出现的概率应恰好等于 $$ \frac {\left( x_1 - 1 \right) ! \left( x_2 - 1 \right) ! \cdots \left( x_n - 1 \right) !} {n \cdot \left( n + 1 \right) \cdots \left( n + d - 1 \right)} $$
于是最终 $\forall i \in \left[ 1, n \right], A_i = x_i$ 的概率就等于 $$ \binom d {x_1 - 1, x_2 - 1, \cdots, x_n - 1} \cdot \frac {\left( x_1 - 1 \right) ! \left( x_2 - 1 \right) ! \cdots \left( x_n - 1 \right) !} {n \cdot \left( n + 1 \right) \cdots \left( n + d - 1 \right)} = \frac {d ! \left( n - 1 \right) !} {\left( d + n - 1 \right) !} = \frac 1 {\dbinom {d + n - 1} {n - 1}} $$
同时为了方便，我们将正整数变成非负整数 (即所有 $a_i$ 减一)。最终原问题被转化为了下列问题：
给定 $n, d$，在所有满足 $x_1 + x_2 + \cdots + x_n = d$ 的非负整数序列中等概率随机一个，求 $x_1, x_2, \cdots, x_n$ 中前 $r$ 大值和的期望。
由于这个期望没什么线性性质能直接利用，那不如索性把所有序列的前 $r$ 大值和的总和计算出来最后除以 $\dfrac 1 {\dbinom {d + n - 1} {n - 1}}$。
那如何计算总和呢？对于和固定且和大小有关的问题，不难想到像拆分数一样进行背包 DP —— 即固定有多少个数等于 $0$，并将剩下的数减 $1$ 转化为子问题 (和 [loj6077]逆序对 比较类似)。
具体地，设 $f_{i, j}$ 表示所有满足 $x_1 + x_2 + \cdots + x_i = j$ 的非负整数序列的前 $r$ 大值的和的总和。
枚举序列中有 $k \in \left[ 0, \min \left\{ i, j \right\} \right]$ 个值非 $0$，那这 $k$ 个非 $0$ 位置有 $\dbinom ik$ 种选择，它们的和要等于 $j - k$。此时我们将这 $k$ 个数减 $1$，就可以一一对应一个 $y_1 + y_2 + \cdots + y_k = j - k$ 的序列。
考虑 $x_1, x_2, \cdots, x_i$ 中的前 $r$ 大值，显然 $0$ 不会对它们的和产生贡献，因此只需考虑 $y_1, y_2, \cdots, y_k$ 中的数。而这部分的贡献分为两类：一类是 $\left\{ y_m \right\}$ 本身的贡献，一部分是加 $1$ 产生的贡献。
$\left\{ y_m \right\}$ 本身的贡献总和显然等于 $f_{k, j - k}$。对于每个序列，加 $1$ 产生的贡献就等于非 $0$ 数的个数 $k$。但由于我们只取前 $r$ 大，因此是 $\min \left\{ k, r \right\}$。
而类似地可以求出满足 $y_1 + y_2 + \cdots + y_k = j - k$ 的非负整数序列总数为 $\dbinom {j - 1} {k - 1}$，综上可得转移方程 $$ f_{i, j} = \sum_{k=0}^{\min \left\{ i, j \right\}} \binom ik \cdot \left( f_{k, j - k} + \min \left\{ k, r \right\} \cdot \binom {j - 1} {k - 1} \right) $$
直接使用 double 计算即可，由于没有减法因此精度不会有较大损失。时间复杂度 $O \left( n d \min \left\{ n, d \right\} \right)$。
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 540;
int n, S, K;
double C[2 * N][N], f[N][N];
int main() {
int i, j, k;
std::ios::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> S >> K;
for (*C[0] = i = 1; i <= S + n; ++i)
for (*C[i] = j = 1; j <= i && j <= n; ++j)
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
for (i = 1; i <= n; ++i)
for (j = 1; j <= S; ++j) {
for (k = 1; k <= K && k <= j; ++k) f[i][j] += C[i][k] * (f[k][j - k] + k * C[j - 1][k - 1]);
for (; k <= i && k <= j; ++k) f[i][j] += C[i][k] * (f[k][j - k] + K * C[j - 1][k - 1]);
}
cout << std::setprecision(12) << f[n][S] / C[S + n - 1][n - 1] + K << '\n';
return 0;
}
坑1：二项式系数可以使用杨辉恒等式预处理，这样精度比较高。
坑2：最后不要忘记加上最初减掉的 $r$。