题意：
有 n个雷，分别在 a[0]...a[n-1] ，走一步概率为 p ，走两步概率为 1-p ，初始位置为1，问安全到达终点的概率。
因为位置范围比较大【1, 100000000】，所以可以把 相邻的两个地雷之间的概率用矩阵快速幂计算
[ a(i) a(i+1) ] *| 0 1-p |=[ a(i+1) a(i+2)]
| 1 p |
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 ",0); 52 continue; 53 } 54 if(pos[0]==2) 55 ans2=0; 56 else 57 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 ",ans1*(1-p)); 72 } 73 }