You probably have played the game “Throwing Balls into the Basket”. It is a simple game. You have to throw a ball into a basket from a certain distance. One day we (the AIUB ACMMER) were playing the game. But it was slightly different from the main game. In our game we were N people trying to throw balls into M identical Baskets. At each turn we all were selecting a basket and trying to throw a ball into it. After the game we saw exactly S balls were successful. Now you will be given the value of N and M. For each player probability of throwing a ball into any basket successfully is P. Assume that there are infinitely many balls and the probability of choosing a basket by any player is 1/M. If multiple people choose a common basket and throw their ball, you can assume that their balls will not conflict, and the probability remains same for getting inside a basket. You have to find the expected number of balls entered into the baskets after K turns. Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing three integers N (1 ≤ N ≤ 16), M (1 ≤ M ≤ 100) and K (0 ≤ K ≤ 100) and a real number P (0 ≤ P ≤ 1). P contains at most three places after the decimal point. Output
For each case, print the case number and the expected number of balls. Errors less than 10-6 will be ignored. Sample Input
Output for Sample Input
2
1 1 1 0.5
1 1 2 0.5
Case 1: 0.5
Case 2: 1.000000
Problem Setter: Muhammad Rifayat Samee Special Thanks: Jane Alam Jan
首先我们要知道每一次扔的时候,0个人扔进的概率,1个人扔进的概率…. 由于最后不关心M个篮子里球的具体情况,所以M其实没有什么用 只要区分扔不扔进去,至于扔到哪个篮子不管 dp[i][j]表示到第i轮,篮子里有j个球的概率 最后答案就是
/*************************************************************************> File Name: L.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年05月17日 星期日 16时05分37秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;double dp[110][1700]; //ith turns, p of j balls double Pa[20];int C[20][20];void init() {C[0][0] = 1;for (int i = 1; i <= 16; ++i) {C[i][0] = 1;C[i][1] = i;for (int j = 2; j < i; ++j) {C[i][j] = C[i – 1][j] + C[i – 1][j – 1];}C[i][i] = 1;}}double Pow(double a, int b) {double ans = 1;for (int i = 1; i <= b; ++i) {ans *= a;}return ans;}int main() {init();int t;int icase = 1;scanf(“%d”, &t);while (t–) {int n, m, k;double p;scanf(“%d%d%d%lf”, &n, &m, &k, &p);memset(dp, 0, sizeof(dp));dp[0][0] = 1;for (int i = 0; i <= n; ++i) {Pa[i] = C[n][i] * Pow(p, i) * Pow((1 – p), n – i);}for (int i = 1; i <= k; ++i) {for (int j = 0; j <= (i – 1) * n; ++j) {for (int l = 0; l <= n; ++l) {if (j + l <= i * n) {dp[i][j + l] += dp[i – 1][j] * Pa[l];}}}}double E = 0;for (int i = 0; i <= k * n; ++i) {E += dp[k][i] * i;}printf(“Case %d: %.12f\n”, icase++, E);}return 0;}
，君子当权积福，小人仗势欺人。
