P6944

概率期望谔谔谔。

#include<bits/stdc++.h>
using namespace std;
double f[1010][1010];
double g[1010][1010];
double C[1010][1010];
int main() {
	int n = ri, d = ri, r = ri;
	C[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for(int j = 1; j <= i; j++)C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	}
	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];
	}
	double 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; 
}