1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdio.h> 5 using namespace std; 6 __int64 t,n,i,j,pos[15],pp; 7 double k,p; 8 struct matrix 9 {10     double arr[15][15];11 } p1,p2,p3;12 matrix add(matrix a,matrix b)//矩阵乘法13 {14     matrix tmp;15     memset(tmp.arr,0,sizeof(tmp.arr));16     for(i=0; i<2; i++)17         for(j=0; j<2; j++){18             for(int k=0; k<2; k++)19                 tmp.arr[i][j]+=a.arr[i][k]*b.arr[k][j];20         }21     return tmp;22 }23 24 matrix fast(matrix a,int n,matrix b)//矩阵快速幂25 {26     while(n>=1)27     {28         if((n&1)!=0)29         {30             b=add(a,b);31         }32         a=add(a,a);33         n/=2;34     }35     return b;36 }37 void init(){38         p1.arr[0][0]=0,p1.arr[0][1]=1-p,p1.arr[1][0]=1,p1.arr[1][1]=p;39         memset(p2.arr,0,sizeof(p2.arr));40         for(int i=0; i<2; i++)41                 p2.arr[i][i]=1;42 }43 int main()44 {45     while(cin>>n>>p)46     {47         for(int i=0;i<n;i++) scanf("%d",&pos[i]);48         sort(pos,pos+n);49         double ans1=1,ans2;50         if(pos[0]==1){51             printf("%.7f\n",0);52             continue;53         }54         if(pos[0]==2)55             ans2=0;56         else57             ans2=p;   58         //初始化第一个位子概率为1，即ans1=1,第二个位置概率要看第一个地雷的位置pos[0]，如果pos[0]=2,则ans2=0,否则ans2=p;59         for(int i=0;i<n;i++){60             int cnt;61             if(i==0) cnt=pos[0]-2;62             else cnt=pos[i]-pos[i-1];63             if(cnt==0) continue;64             init();65             p3=fast(p1,cnt,p2);66             double t1,t2;67             t1=ans1*p3.arr[0][0]+ans2*p3.arr[1][0];68             t2=ans1*p3.arr[0][1]+ans2*p3.arr[1][1];69             ans1=t1,ans2=0;70         }71         printf("%.7f\n",ans1*(1-p));72     }73 }