Light OJ 1317 Throwing Balls into the Baskets 概率DP

Light OJ 1317 Throwing Balls into the Baskets 概率DP

n個人 m個籃子 每一輪每個人可以選m個籃子中一個扔球 扔中的概率都是p 求k輪後所有籃子裡面球數量的期望值

根據全期望公式 進行一輪球數量的期望值為dp[1]*1+dp[2]*2+...+dp[n]*n 記為w

其中dp[i]為i個人扔中的概率 dp[i] = C(n, i)*p^i*(1-p)^(n-i) 最終答案為w*k

#include 
#include 
using namespace std;
double dp[20];
double a[20], b[20];

double cm(int n, int m)
{
	double ans = 1;
	for(int i = 1; i <= m; i++)
	{
		ans *= (double)n--;
		ans /= (double)i;
	}
	return ans;
}
int main()
{
	int T;
	int cas = 1;
	scanf("%d", &T);
	while(T--)
	{
		int n, m, k;
		double p;
		scanf("%d %d %d %lf", &n, &m, &k, &p);
		dp[0] = a[0] = b[0] = 1;
		for(int i = 1; i <= n; i++)
		{
			a[i] = a[i-1]*p;
			b[i] = b[i-1]*(1-p);
		}
		for(int i = 0; i <= n; i++)
		{
			dp[i] = cm(n, i)*a[i]*b[n-i];
		}
		double ans = 0;
		for(int i = 1; i <= n; i++)
			ans += dp[i]*(double)i;
		ans *= (double)k;
		printf("Case %d: %.10lf\n", cas++, ans);
	}
	return 0;
}