UVA 11021 - Tribles

题目链接

题意：k个毛球，每一个毛球死后会产生i个毛球的概率为pi。问m天后，全部毛球都死亡的概率

思路：f[i]为一个毛球第i天死亡的概率。那么

f(i)=p0+p1f(i−1)+p2f(i−1)2+...+pnf(i−1)n

然后k个毛球利用乘法定理，答案为f(m)k

代码：

#include <stdio.h>

#include <string.h>

#include <math.h>

const int N = 1005;

int t, n, k, m;

double p[N], f[N];

int main() {

	int cas = 0;

	scanf("%d", &t);

	while (t--) {

		scanf("%d%d%d", &n, &k, &m);

		for (int i = 0; i < n; i++)

			scanf("%lf", &p[i]);

		f[0] = 0; f[1] = p[0];

		for (int i = 2; i <= m; i++) {

			f[i] = 0;

			for (int j = 0; j < n; j++)

				f[i] += p[j] * pow(f[i - 1], j);

  		}

  		printf("Case #%d: %.7lf\n", ++cas, pow(f[m], k));

 	}

	return 0;

}