题意:有T个队伍,有M道题,要求每个队至少有一道题,并且有队伍至少过N道题的概率。
这个题解主要讲一下,后面的,至少有一道题解决和至少一道题至N-1道题解决,到底怎么算的,其实,很简单,就是母函数。
ac代码:
#include#define N 1001#define T 31double dp[N][T][T];double p[N][T];int main(){ int m, t, n; while (scanf("%d%d%d", &m, &t, &n) != EOF, m || n || t) { for (int i = 1; i <= t;++i) for (int j = 1; j <= m; ++j) scanf("%lf", &p[i][j]); for (int i = 1; i <= t; ++i) { dp[i][0][0] = 1; for (int j = 1; j <= m;++j) for (int k = 0; k <= j; ++k) { dp[i][j][k] = dp[i][j-1][k] * (1 - p[i][j]); if (k != 0)dp[i][j][k]+=dp[i][j-1][k - 1] * p[i][j]; } } double p1 = 1; //利用母函数 for (int i = 1; i <= t; ++i) { double ans = 0; for (int k = 1; k <= m; ++k) ans += dp[i][m][k]; p1 *= ans; } double p2 = 1; for (int i = 1; i <= t; ++i) { double ans = 0; for (int k = 1; k < n; ++k) ans += dp[i][m][k]; p2 *= ans; } printf("%.3lf\n", p1 - p2); }}