题意:一条路上有n个地雷，告诉你这n个雷的位置，一个人初始在位置1，这个人每次可以走1个单位或者跳2个单位，概率分别为p和1-p，现在要求这个人安全通过这段路的概率
思路：求出安全通过每个雷的概率，再把所有的乘起来即可。要安全通过某个雷（假设在place[i]这个位置），只有从place[i]-1跳两格才能安全通过。这样只要求出place[i-1]+1到place[i]-1的概率再乘上(1-p)就能得到通过第i个雷的概率。
由于数据较大，所以必须用矩阵快速幂。其实这是斐波拉契数列的一个变形：f(i)=f(i-1)*p+f(i-2)*(1-p) ;要快速求出f(i),使用矩阵快速幂即可。
#include#include #include #include using namespace std;int place[1010] ;double ep[1010] , p ,f1 ,f2;struct Mat{ double mat[10][10] ;};Mat mul(Mat a,Mat b){ Mat ret; for(int i=0;i<2;i++) for(int j=0;j<2;j++) { ret.mat[i][j]=0; for(int k=0;k<2;k++) ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; } return ret;}Mat pow_M(Mat a,int n){ Mat ret; memset(ret.mat,0,sizeof(ret.mat)); for(int i=0;i<2;i++)ret.mat[i][i]=1; Mat temp=a; while(n) { if(n&1)ret=mul(ret,temp); temp=mul(temp,temp); n>>=1; } return ret;}double Q_mul(int k){ Mat a; a.mat[0][0]=p, a.mat[0][1]=1.0-p ,a.mat[1][0]=1.0 ,a.mat[1][1]=0; Mat ret=pow_M(a,k); return (f2*ret.mat[1][0]+f1*ret.mat[1][1])*(1.0-p);}int main(){ int n; while(cin>>n>>p){ memset(place,0,sizeof(place)) ; for(int i=0;i