首页 > 代码库 > 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