Uva_11021 Tribles
题意：
现在有k只麻球， 每只麻球只能存活一天， 第二天就会死去， 死去之前可能生下x只小麻球(x = 0,1,2,...,n 1), 概率分别为P[0], P[1], ... , P[n - 1]。
现求， m天之后， 所有麻球全死去的概率， 包括m天之前就已经全部死去。
思路:
每只麻球都是相互独立的， 那么 可以先算初始只有一只麻球，m天之内全部死去的概率。
设f(x) 为 初始只有一只麻球， x天后全部死去的概率。
得：
f(x) = P[0] * f(x - 1)^0 + P[1] * f(x - 1) + P[2] * f(x-1)^2 + .. + P[n - 1] * f(x - 1)^(n - 1)。
P[j]为一只麻球生下j只小麻球的概率， 又因为所有的麻球都要在x天之内全部死去， 所以 这j只小麻球需要在x - 1天全部死去， 而每只麻球相互独立， 所以概率相乘。
得：
初始条件：f[0] = P[0]。
递推得到f[m]， 答案即为f[m] ^ k。
代码如下：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 1010
19 #define MOD 1000000007
20 #define eps 1e-6
21 int n, k, m;
22 double P[MAXN];
23 double f[MAXN];
24 double qpow(double x, int k)
25 {
26 double res = 1.0;
27 while(k)
28 {
29 if(k & 1) res = res * x;
30 x = x * x;
31 k >>= 1;
32 }
33 return res;
34 }
35 void init()
36 {
37 memset(f, 0, sizeof(f));
38 f[0] = 0;
39 f[1] = P[0];
40 for(int x = 2; x <= m; x ++)
41 for(int j = 0; j < n; j ++)
42 f[x] = f[x] + P[j] * qpow(f[x - 1], j);
43 }
44
45 int main()
46 {
47 int T;
48 int kcase = 0;
49 scanf("%d", &T);
50 while(T --)
51 {
52 scanf("%d %d %d", &n, &k, &m);
53 for(int i = 0; i < n; i ++)
54 scanf("%lf", &P[i]);
55 init();
56 printf("Case #%d: %.7lf\n", ++ kcase, qpow(f[m], k));
57 }
58 return 0;
59 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-07-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读