题目相当于：有个序列({a_i})，一开始全(0)。有(d)次操作，每次随机地选一个(i)，概率为(frac{a_i}{sum a_i})，然后将(a_i)变成(a_i+1)。
求最终前(r)个期望是多少。
答案输出小数。
早就想到了大概的思路，但因为答案输出小数而不是取模迟迟不敢下手。因为这题在计数过程中铁定会出现很大的数的，然后最后再除以一个很大的组合数。看起来精度问题就很可怕。
后来翻翻题解发现原来没有任何精度的问题。。
假如最后形成的有序序列为({a_i})，得到它的概率为(frac{1}{prod_{i=n}^{n+d-1}i}prod a_i!frac{(sum a_i)!}{prod a_i!})，即(frac{1}{inom{n+d-1}{n}})。
于是只需要统计每个有序序列的贡献。转化成统计无序序列（排序后）的方案数和贡献。
有如此DP：(f_{i,j})表示(i)个数和为(j)的方案数，(g_{i,j})为(i)个数和为(j)的前(r)个数的和。
转移考虑枚举(k)，(k)个至少为(1)，(i-k)个恰好为(0)。
于是有(f_{k,j-k}inom{i}{k} o f_{i,j})和(g_{k,j-k}inom{i}{k}+f_{k,j-k}inom{i}{k}min(k,r) o g_{i,j})
直接用long double算没有爆精度，佩服。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define db long double
#define N 1005
int n,d,r;
db C[N][N];
void initC(int n){
for (int i=0;i<=n;++i){
C[i][0]=1;
for (int j=1;j<=i;++j)
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
db f[N][N],g[N][N];
int main(){
scanf("%d%d%d",&n,&d,&r);
initC(n+d);
f[0][0]=1,g[0][0]=0;
for (int i=1;i<=n;++i){
for (int j=0;j<=d;++j)
for (int k=0;k<=j && k<=i;++k){
f[i][j]+=f[k][j-k]*C[i][k];
g[i][j]+=g[k][j-k]*C[i][k]+min(k,r)*f[k][j-k]*C[i][k];
}
}
printf("%.7lf
",(double)(g[n][d]/C[n+d-1][d])+r);
return 0;
}