首页 > 代码库 > POJ 3744
POJ 3744
矩阵快速乘求概率,不难。但有注意的一点是,一定要注意地雷连着的情况,一旦出现两个雷相邻,就必定为0了。
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;int pos[15];struct matrix{ double m[3][3];};matrix per,pt,ps;matrix operator *(matrix a,matrix b){ matrix c; for(int i=1;i<=2;i++){ for(int j=1;j<=2;j++){ c.m[i][j]=0; for(int k=1;k<=2;k++) c.m[i][j]+=(a.m[i][k]*b.m[k][j]); } } return c;}matrix quick(int k){ matrix ans=per,p=pt; while(k){ if(k&1) ans=ans*p; k>>=1; p=p*p; } return ans;}int main(){ int n; double p; while(scanf("%d%lf",&n,&p)!=EOF){ memset(per.m,0,sizeof(per.m)); per.m[1][1]=per.m[2][2]=1; memset(pt.m,0,sizeof(pt.m)); pt.m[1][1]=p;pt.m[2][1]=1; pt.m[1][2]=1-p; memset(ps.m,0,sizeof(ps.m)); ps.m[1][1]=p; ps.m[2][1]=1; for(int i=1;i<=n;i++) scanf("%d",&pos[i]); sort(pos+1,pos+n+1); if(pos[1]==1){ printf("%.7lf\n",0); continue; } pos[0]=0; matrix tmp; double ans=1; for(int i=1;i<=n;i++){ int g=pos[i]-1-pos[i-1]-1; if(g>0){ tmp=quick(g-1); tmp=tmp*ps; ans=ans*tmp.m[1][1]; } if(pos[i+1]==pos[i]+1){ ans=0; break; } ans*=(1-p); } printf("%.7lf\n",ans); } return 0;}
POJ 3744
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。