/*poj 2096
第一道概率dp看别人的思路，不过总算理解为什么求期望从后往前了
地址：http://blog.csdn.net/morgan_xww/article/details/6774708
*/
#include<stdio.h>
#include<string.h>
#define N 1100
double dp[N][N];
int main() {
int n,s,i,j;
while(scanf("%d%d",&n,&s)!=EOF) {
memset(dp,0,sizeof(dp));
for(i=n;i>=0;i--)
for(j=s;j>=0;j--) {
if(i==n&&j==s)continue;
dp[i][j]=(n*s+dp[i+1][j]*(n-i)*j+dp[i][j+1]*i*(s-j)+dp[i+1][j+1]*(n-i)*(s-j))/(n*s-i*j);
}
printf("%.4f
",dp[0][0]);
}
return 0;}
/*
hdu 3853
有一个坑，到达自身的概率为1的话，就不用加到上一个
*/
#include<stdio.h>
#include<math.h>
#include<string.h>
#define eps 1e-10
#define N 1100
struct node {
double a,b,c;
}ma[N][N];
double dp[N][N];
int main() {
int n,m,i,j;
while(scanf("%d%d",&n,&m)!=EOF) {
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%lf%lf%lf",&ma[i][j].a,&ma[i][j].b,&ma[i][j].c);
memset(dp,0,sizeof(dp));
for(i=n-1;i>=0;i--)
for(j=m-1;j>=0;j--) {
if(i==n-1&&j==m-1)continue;
if(fabs(1-ma[i][j].a)<eps)continue;//对于不能到达的不用计算
dp[i][j]=(dp[i+1][j]*ma[i][j].c+dp[i][j+1]*ma[i][j].b+2)/(1-ma[i][j].a);
}
printf("%.3f
",dp[0][0]);
}
return 0;}
/*
hdu 4405
只需处理以下可以直接到达的关系就可以了
*/
#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
#define N 110000
double dp[N];
int f[N];
int main() {
int n,m,i,a,b;
double kk;
while(scanf("%d%d",&n,&m),n||m) {
memset(dp,0,sizeof(dp));
memset(f,-1,sizeof(f));
while(m--) {
scanf("%d%d",&a,&b);
f[a]=b;
}
for(i=n-1;i>=0;i--) {
if(f[i]==-1)
dp[i]=dp[i+1]/6+dp[i+2]/6+dp[i+3]/6+dp[i+4]/6+dp[i+5]/6+dp[i+6]/6+1.0;
else
dp[i]=dp[f[i]];
}
printf("%.4f
",dp[0]);
}
return 0;}
/*
sgu495
m个人是独立的
n个礼物每一个都不被选中的概率是(n-1)/n;
n个礼物都不被选中的期望为n*pow(d,m);
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 1100
int main() {
int n,m;
double d,sum;
while(scanf("%d%d",&n,&m)!=EOF) {
d=(double)(n-1)/n;
sum=1.0*n-1.0*n*pow(d,m);
printf("%.10f
",sum);
}
return 0;}
/*
sgu495
第二种做法很好
m个人是独立的
从人考虑：
每个人都有可能得到1个礼物，但是第i个人得到1个礼物的概率与第i-1个人得到礼物的概率有关
如果第i-1个人的到礼物，那么第i个人得到1个礼物的概率为dp[i-1]*(dp[i-1]-1.0/n);
如果第i-1个人没有得到，那么第i个人得到1个礼物的概率为dp[i-1]*(1-dp[i-1]);
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 110000
double dp[N];
int main() {
int n,m,i;
double d,sum;
while(scanf("%d%d",&n,&m)!=EOF) {
dp[1]=1.0;sum=0;
for(i=2;i<=m;i++) {
dp[i]=1*((1-dp[i-1])*dp[i-1])+1*(dp[i-1]*(dp[i-1]-1.0/n));
sum+=dp[i];
}
printf("%.10f
",sum+1.0);
}
return 0;}
/*
cf 148D
理解概率的从前到后处理很好！
先确定边界，从边界出发进行dp
题意：王妃和龙轮流从袋子里那老鼠，如果王妃先拿到白老鼠，如果龙先拿到白老鼠那么龙赢，那么王菲赢，如果两人都没有取到
白老鼠那么龙赢.
求概率从前往后，先处理边界，
参考博客：http://www.cnblogs.com/kuangbin/archive/2012/10/04/2711184.html
dp[i][j]代表剩余i只白鼠j只黒鼠时王妃赢的概率
三种情况王妃赢
1.王妃抓到一只白老鼠，王菲赢了i/(i+j);
2.w王妃抓到一只黑老鼠，龙抓到一只黑老鼠，跑了一只黑老鼠,那么赢的概率需要用到dp[i][j-3];
1.0*j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];
3.王菲抓到一只黑老鼠，龙抓到一只黑老鼠，跑了一只白老鼠，那么赢的概率需要用到dp[i-1][j-2]
1.0*j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2]
并且保证合法
*/
#include<stdio.h>
#include<string.h>
#define N 1100
double dp[N][N];
int main() {
int n,m,i,j;
while(scanf("%d%d",&n,&m)!=EOF) {
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)dp[i][0]=1;
for(i=1;i<=m;i++)dp[0][i]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) {
dp[i][j]+=1.0*i/(i+j);
if(j>=2)
dp[i][j]+=1.0*j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2];
if(j>=3)
dp[i][j]+=1.0*j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];
}
printf("%.10f
",dp[n][m]);
}
return 0;}
/*
题意：
一只吸血鬼，有n条路给他走，每次他随机走一条路，
每条路有个限制，如果当时这个吸血鬼的攻击力大于
等于某个值，那么就会花费t天逃出去，否则，花费1天
的时间，并且攻击力增加，问他逃出去的期望天数
因为可能有许多种情况，并且可以重复出现，所以记忆化搜索
比如在某些条件下f+a[1]+a[2]和f+a[2]+a[1]，会重复出现所以记忆
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 21000//因为f和a[i]的值都是10000所以
double dp[N];
int a[N];
int n;
double dfs(int f)
{
if(dp[f]>0)return dp[f];
int i;
for(i=1; i<=n; i++)
{
if(f>a[i])
{
double temp=(1.0+sqrt(5.0))/2*a[i]*a[i];
int t=(int)temp;
dp[f]+=1.0*t*1.0/n;
}
else
dp[f]+=(1.0+dfs(f+a[i]))*1.0/n;//当前能够走出去的天数由f+a[i]后的期望天数+1乘于概率得到
}
return dp[f];
}
int main()
{
int m,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1; i<=n; i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
printf("%.3f
",dfs(m));
}
return 0;
}
/*
poj 3744 求概率
题意：侦察兵YYF要通过一条布有地雷的路，
他从1出发，每次有p的几率前进1格，
1-p的几率前进两个，现已知所有地雷的位置，求YYF不踩中地雷并且通过这条雷区路的的概率
解：首先特判如果1的点是雷的话直接炸死
易知初始化dp[0]=0;dp[1]=1;
dp[i]=dp[i-1]*p+dp[i-2]*(1-p);
因为i很大所以用矩阵快速幂解
构建矩阵
|a0,a1|*|0 1-p| =|a1 a2|
|1 p |
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 10
int aa[N];
struct matrix{
double mat[5][5];
};
matrix matmul(matrix a,matrix b) {
int i,j,k;
matrix c;
memset(c.mat,0,sizeof(c.mat));
for(i=0;i<2;i++)
for(j=0;j<2;j++)
for(k=0;k<2;k++)
c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
return c;
}
matrix matpow(matrix a,int k) {
matrix b;
int i;
memset(b.mat,0,sizeof(b.mat));
for(i=0;i<2;i++)
b.mat[i][i]=1;
while(k) {
if(k&1)b=matmul(a,b);
a=matmul(a,a);
k>>=1;
}
return b;
}
int main() {
int n,i,k,flag;
double p;
while(scanf("%d%lf",&n,&p)!=EOF) {
flag=0;
for(i=1;i<=n;i++) {
scanf("%d",&aa[i]);
if(aa[i]==1)
flag=1;
}
if(flag) {
printf("%.7f
",0);
continue;
}
sort(aa+1,aa+1+n);
matrix a,b;
memset(a.mat,0,sizeof(a.mat));
a.mat[0][0]=0;
a.mat[0][1]=1.0;
b.mat[0][0]=0;
b.mat[0][1]=1-p;
b.mat[1][0]=1.0;
b.mat[1][1]=p;
aa[0]=1;
for(i=1;i<=n;i++) {
k=aa[i]-aa[i-1]-1;
a=matmul(a,matpow(b,k));
a.mat[0][0]=a.mat[0][1];
a.mat[0][1]=0;
}
a=matmul(a,matpow(b,1));
printf("%.7f
",a.mat[0][1]);
}
return 0;}