求概率
uva11021 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1962
给定n，k，m
有k个麻雀，每只活一天就会死，临死之前生出i只麻雀的概率为pi ， 0<= i <n
问m天后，麻雀死光的概率
独立事件同时发生是每个事件的概率相乘， 每只麻雀都是独立的，只要求出一只麻雀m天后死亡的概率dp[m]， 那么k只麻雀m天后死亡的概率为dp[m]^k
dp[i]表示i天后麻雀全部死亡的概率， 这个全部死亡即自己死亡，后代也死亡
dp[i]可以分解为n个子事件，生0->n-1个孩子，如果生j个孩子，那么j个孩子要在i-1天后死亡，这样全部的麻雀才会在i天后死亡，j个孩子要在i-1天后死亡是独立事件同时发生
所以是dp[i-1]^j,生j个孩子的概率为pj, 所以生j个孩子且i-1天后死亡也是独立事件，概率为pj * dp[i-1]^j
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/*
f[i] = p0
*/
const int N = + ;
double p[N],dp[N];
int main()
{
int n, k, m, t, tCase = ;
scanf("%d", &t);
while (tCase <= t)
{
scanf("%d%d%d", &n, &k, &m);
for (int i = ; i < n; ++i)
scanf("%lf", &p[i]);
dp[] = ;//0天后死亡是不可能的，所以概率是0
dp[] = p[];//一天后死亡的概率是不生孩子的概率
for (int i = ; i <= m; ++i)
{
dp[i] = ;
for (int j = ; j < n; ++j)
dp[i] += p[j] * pow(dp[i - ], j);
}
printf("Case #%d: %.7lf\n", tCase++, pow(dp[m], k));
}
return ;
}
http://acm.hit.edu.cn/hoj/problem/view?id=2866
给定n，m 表示第一个人的血量和第二个人的血量
然后接下来两行，每行6个数字，分别表示摇骰子得到点数1->6的概率
要我们求第一个人赢的概率
p1,p2,p 表示进行一次游戏，第一个人赢，第二个人赢，平局的概率
q1,q2表示前n局中，第一个人赢一局，其他都是平局， 第二个人赢一局，其他都是平局的概率,如图
q1 = p1/(1-p)
q2 = p2/(1-p)
dp[i][j] 表示第一个人赢i次，第二个人赢j次， dp[i][j] = dp[i-1][j]*q1 + dp[i][j-1]*q2
为什么是dp[i][j] = dp[i-1][j]*q1 + dp[i][j-1]*q2;
而不是 dp[i][j] = dp[i-1][j]*p1 + dp[i][j-1]*p2;
因为进行一局游戏，有第一个人赢，第二个人赢，平局
不可能理想到只进行了一次游戏，就可能第一个人赢 即dp[i-1][j]*p1,
所以要一个人赢一局，可能经过了n局，然后才赢一局， q1,q2就是经过了很多平局，才赢得一局的情况
答案是dp[hp2][0->hp1-1]
初始化条件是dp[0][0] = 1，这是必然的，因为刚开始的，必定两个人都没有赢过一次，所以是1，必定发生
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */
double dp[][];
int main()
{
int hp1, hp2;
double a[], b[];
int i, j;
double p1, p2, p, q1, q2;
while (scanf("%d%d", &hp1, &hp2) != EOF)
{
p1 = p2 = p = q1 = q2 = ;
for (i = ; i < ; ++i)
scanf("%lf", &a[i]);
for (i = ; i < ; ++i)
scanf("%lf", &b[i]);
for (i = ; i < ; ++i)
for (j = ; j < i; ++j)
{
p1 += a[i] * b[j];
p2 += a[j] * b[i];
}
p = 1.0 - p1 - p2;
p == ? q1 = q2 = : q1 = p1 / ( - p), q2 = p2 / ( - p);
//q1 = p1 / (1.0 - p);
//q2 = p2 / (1.0 - p);
memset(dp, , sizeof(dp));
dp[][] = 1.0;
for (i = ; i <= hp2; ++i)
{
for (j = ; j <= hp1; ++j)
{
if (j<hp1 && i) dp[i][j] += dp[i - ][j] * q1;
if (i<hp2 && j) dp[i][j] += dp[i][j - ] * q2;
}
}
double ans = ;
for (j = ; j < hp1; ++j)
ans += dp[hp2][j];
printf("%.6lf\n", ans);
}
return ;
}
poj 2151 http://poj.org/problem?id=2151
m t n
m到题目， t个队伍， n 冠军队最少解决n道题
t行，每行m个数字
表示每个队伍解决第i道题目的概率
问我们每个队伍至少解决一题，且冠军队至少解决n题的概率
p1为每个队伍至少解决一题的概率
p2为每个队伍解决k题的概率 1<=k<n
最终答案为p1-p2,每个队伍至少做出一题，且冠军队至少解决n题的概率
单独算出队伍至少解决k题的概率，每只队伍的概率相乘（独立事件同时发生）
dp[i][j][k] 为第i只队伍前j道题目解出k题的概率 dp[i][j][k] = dp[i][j-1][k-1] * p[i][j] + dp[j-1][k] *(1-p[i][j])
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */
double p[+][+];
double dp[ + ][ + ];
double s[];
int main()
{
int n, m, t, i, j, k;
while (scanf("%d%d%d", &m, &t, &n), m+n+t)
{
double p1, p2, tmp;
p1 = p2 = ;
for (i = ; i <= t; ++i)
{
tmp = ;
for (j = ; j <= m; ++j)
{
scanf("%lf", &p[i][j]);
tmp = tmp * ( - p[i][j]);//tmp为一题都没做出来的概率
}
p1 = p1*( - tmp);//p1为每个队伍至少做出一题的概率
}
for (i = ; i <= t; i++)
{
//dp[0][0] = 1;
memset(dp, , sizeof(dp));
dp[][] = ;
//for (j = 1; j <= m; ++j)
// dp[j][0] = dp[j - 1][0] * (1 - p[i][j]);
for (j = ; j <= m; ++j)
{
dp[j][] = dp[j - ][] * ( - p[i][j]);
for (k = ; k <=j; ++k)
{
dp[j][k] += dp[j - ][k] * ( - p[i][j]);
//if (k!=0)
dp[j][k] += dp[j - ][k - ] * p[i][j];
}
}
tmp = ;
for (k = ; k < n; ++k)
tmp += dp[m][k];
p2 = p2 * tmp;
}
printf("%.3f\n", p1 - p2);
}
return ;
}
poj3071 http://poj.org/problem?id=3071
给定一个n， 表示有2^n个队伍进行比赛
给定一个2^n * 2^n的矩形
pij 表示第i队伍打败第j只队伍的概率
比赛的规则是第一只队伍和第二只打，第三只队伍和第四只打，赢的晋级，然后还是依照这样的规则，如图
要我们求哪只队伍最终获胜的概率最大，输出该队伍
dp[i][j] 表示第i次比赛，队伍j获胜， 设k为要与j比赛的队伍 dp[i][j] += sum(dp[i-1][j] * dp[j-1][k] * p[j][k] )
那么怎么判断所要与j比赛的，我们对队伍进行分组， 队伍号/(i<<(i-1)) 就是组号了， 如果是组号是偶数，那么要与后一只队伍比赛，如果是奇数，那么要与前一只队伍比赛
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */
double dp[][], p[][];
int main()
{
int n, i, j, k;
while (scanf("%d", &n), n != -)
{
int m = << n;
for (i = ; i < m; ++i)
for (j = ; j < m; ++j)
scanf("%lf", &p[i][j]);
for (i = ; i < m; ++i)
dp[][i] = ;//dp[i][j]表示第i次比赛，获胜者是j的概率
for (i = ; i <= n; ++i)//2^n个队伍每次淘汰一半的队伍，所以要进行n次比赛才能决出胜负
{
int t = << (i-);
for (j = ; j < m; ++j)
{
dp[i][j] = ;
int teamNumWin = j / t;//分组
for (k = ; k < m; ++k)
{
int teamNumLose = k / t;//分组
if (teamNumWin % == && teamNumWin + == teamNumLose)//如果组数是偶数，那么与后一组比赛
dp[i][j] += dp[i - ][j] * dp[i - ][k] * p[j][k];
if (teamNumWin % == && teamNumWin - == teamNumLose)//如果组数是奇数，与前一组比赛
dp[i][j] += dp[i - ][j] * dp[i - ][k] * p[j][k];
}
} }
double Max = ;
int ans;
for (i = ; i < m; ++i)
if (dp[n][i]>Max)
{
Max = dp[n][i];
ans = i;
}
printf("%d\n", ans + );
}
return ;
}
http://codeforces.com/problemset/problem/148/D
给定w,b 分别为袋子里白老鼠和黑老鼠的数量
先取到白老鼠的人赢，一轮游戏后，即两个人各取了一只后，会从带子里随机逃出一只老鼠，老鼠逃出的概率是均等的。
问第一个人赢的概率
dp[i][j] 表示有i只白鼠，j只黑鼠的时候，第一个人赢的概率
这个人可能这一轮就赢，即取到白老鼠dp[i][j] += i/(i+j);
也可能下一轮才赢，那么这一轮可能的情况是：
第一个人取到黑，第二个人取到黑，逃掉一只黑的 dp[i][j] += j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];
第一个人取到黑，第二个人取到黑，逃掉一只白的 dp[i][j] += j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2];
还有一种可能是
第一个人取到黑，第二个人取到白， 但这不是我们要考虑的，我们要考虑的是第一个人赢的概率
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/*
dp[i][j] 表示有i只白鼠，j只黑鼠的时候，princess赢的概率
dp[i][j] = i/(i+j) + j/(i+j) * (j-1)/(i+j-1) * (j-2)/(i+j-2) * dp[i][j-3] + j/(i+j) * (j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2]
*/
double dp[ + ][ + ];
int main()
{
int w, b, i, j;
scanf("%d%d", &w, &b);
for (i = ; i <= w; ++i)
dp[i][] = ;//如果只有白，没有黑，那么第一次抓就会赢
for (i = ; i <= w; ++i)
{
for (j = ; j <= b; ++j)
{
dp[i][j] += (double)i / (i + j);
if (j >= )
dp[i][j] += (double)j / (i + j) * (double)(j - ) / (i + j - ) * (double)(j - )/(i + j - )*dp[i][j - ];
if (j >= )
dp[i][j] += (double)j / (i + j) * (double)(j - ) / (i + j - ) * (double)i / (i + j - )*dp[i - ][j - ];
} }
printf("%.9lf\n", dp[w][b]);
return ;
}
poj http://poj.org/problem?id=3744
给定n, p 表示有n个地雷，p表示人走一步的概率，1-p表示人跳两步的概率， 人的其实位置在1
接下来n个数字表示n个地雷的位置， （地雷的位置不是递增的，坑爹啊）
我们求人安全走出雷区的概率
状态转移方程很简单dp[1] = 1 , 如果i不是雷区， dp[i] = dp[i-1] * p + dp[i-2] * (1-p), 如果i是雷区， dp[i]=0
但是雷区的长度实在是太长了，而这又是一个递推关系，所以我们可以用矩阵来优化
1--a[1]
a[1] + 1--a[2]
...进行分段
首先用矩阵快速幂求的dp[a[1]] ，dp[a[1]-1]
从而求的dp[a[1]+1] ,dp[a[1]]，然后进行第二段矩阵快速幂，依次类推。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */
class Matrix
{
public :
double mat[][];
void makeZero()
{
for (int i = ; i < ; ++i)
for (int j = ; j < ; ++j)
mat[i][j] = ;
}
void makeUnit()
{
for (int i = ; i < ; ++i)
for (int j = ; j < ; ++j)
mat[i][j] = (i == j);
}
};
Matrix operator*(const Matrix &lhs, const Matrix &rhs)
{
Matrix ret;
ret.makeZero();
for (int k = ; k < ; ++k)
for (int i = ; i < ; ++i)
{
if (lhs.mat[i][k] == ) continue;
for (int j = ; j < ; ++j)
ret.mat[i][j] += lhs.mat[i][k] * rhs.mat[k][j];
}
return ret;
}
Matrix operator^(Matrix a, int n)
{
Matrix ret;
ret.makeUnit();
while (n)
{
if (n & )
ret = ret * a;
n >>= ;
a = a * a;
}
return ret;
}
int a[ + ];
int main()
{
int n, i, x;
double p;
int pre;
Matrix aa;
double f1, f2;
while (scanf("%d%lf", &n, &p) != EOF)
{
bool flag = false;
for (i = ; i <= n; ++i)
{
scanf("%d", &a[i]);
if (a[i] - a[i - ] == )
flag = true;
}
sort(a + , a + n + );
for (i = ; i <= n; ++i)
if (a[i] - a[i - ] == )
flag = true;
if (flag)
printf("%.7lf\n", );
else
{
pre = ;
f1 = ;
f2 = ;
for (i = ; i <= n; ++i)
{
aa.mat[][] = p;
aa.mat[][] = ;
aa.mat[][] = - p;
aa.mat[][] = ;
aa = aa ^ (a[i] - pre);
pre = a[i]+; //double tmpf2 = f2 * aa.mat[0][0] + f1*aa.mat[1][0];
//double tmpf1 = f2 * aa.mat[0][1] + f1*aa.mat[1][1];
//f2 = tmpf2;
//f1 = tmpf1;
//f2 = f1 * (1 - p);
//f1 = 0;
//这是根据上面的注释的代码推出来的
f2 = f2 * aa.mat[][] * ( - p);
}
printf("%.7f\n", f2);
}
}
return ;
}
uva10759 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1700
给定n个骰子和数字x，要我们求掷n个骰子，点数至少为x的概率
dp[i][j] 为前i个骰子，点数为j的概率 dp[i][j] += dp[i-1][j-k]/6 j-k>=0, 初始条件dp[0][0] = 1;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef unsigned long long LL;
const int INF = <<;
/* */
struct node//因为要输出分数，所以建立一个数据结构，存分子和分母
{
LL x, y;//x/y
};
node dp[][];
LL gcd(LL a, LL b)
{
if (b == )
return a;
return gcd(b, a%b);
}
int main()
{
int n, x;
while (scanf("%d%d", &n, &x), n || x)
{
memset(dp, , sizeof(dp));
dp[][].x = dp[][].y = ;
int m = n * ;
for (int i = ; i <= n; ++i)
{
for (int j = i; j <= m; ++j)
{
for (int k = ; k <= ; ++k)
if (j - k >= && dp[i - ][j - k].y != )
{
if (dp[i][j].y == )
{
dp[i][j] = dp[i - ][j - k];
dp[i][j].y *= ;
continue;
}
LL y = dp[i - ][j - k].y * ;
LL g = gcd(dp[i][j].y, y);
LL tmp = dp[i][j].y / g * y;
dp[i][j].x = dp[i][j].x * (tmp / dp[i][j].y) + dp[i - ][j - k].x*(tmp / y);
dp[i][j].y = tmp;
//dp[i][j] += dp[i - 1][j - k] / 6;
}
}
} node ans = dp[n][x];
for (int i = x + ; i <= m; ++i)
{
if (dp[n][i].y == ) continue;
if (ans.y == )
{
ans = dp[n][i];
continue;
}
LL g = gcd(ans.y, dp[n][i].y);
LL tmp = ans.y / g * dp[n][i].y;
ans.x = ans.x *(tmp / ans.y) + dp[n][i].x*(tmp / dp[n][i].y);
ans.y = tmp;
}
LL g = gcd(ans.x, ans.y);
if (g != )
{
ans.x /= g;
ans.y /= g;
}
if (ans.y != )
{
if (ans.x%ans.y == )
printf("%llu\n", ans.x / ans.y);
else
printf("%llu/%llu\n", ans.x, ans.y);
}
else
printf("0\n");
}
return ;
}
下面的是求期望的