题意：在一条不满地雷的路上，你现在的起点在1处。在N个点处布有地雷，1<=N<=10。地雷点的坐标范围：[1,100000000].
每次前进p的概率前进一步，1-p的概率前进1-p步。问顺利通过这条路的概率。就是不要走到有地雷的地方。
设dp[i]表示到达i点的概率，则 初始值 dp[1]=1.
很容易想到转移方程： dp[i]=p*dp[i-1]+(1-p)*dp[i-2];
但是由于坐标的范围很大，直接这样求是不行的，而且当中的某些点还存在地雷。
N个有地雷的点的坐标为 x[1],x[2],x[3]```````x[N].
我们把道路分成N段：
1~x[1];
x[1]+1~x[2];
x[2]+1~x[3];
`
`
`
x[N-1]+1~x[N].
这样每一段只有一个地雷。我们只要求得通过每一段的概率。乘法原理相乘就是答案。
对于每一段，通过该段的概率等于1-踩到该段终点的地雷的概率。
就比如第一段 1~x[1]. 通过该段其实就相当于是到达x[1]+1点。那么p[x[1]+1]=1-p[x[1]].
但是这个前提是p[1]=1,即起点的概率等于1.对于后面的段我们也是一样的假设，这样就乘起来就是答案了。
对于每一段的概率的求法可以通过矩阵乘法快速求出来。
1 /* 2 POJ 3744 3 4 C++ 0ms 184K 5 */ 6 #include<stdio.h> 7 #include<string.h> 8 #include<algorithm> 9 #include<iostream> 10 #include<math.h> 11 using namespace std; 12 13 struct Matrix 14 { 15 double mat[2][2]; 16 }; 17 Matrix mul(Matrix a,Matrix b) 18 { 19 Matrix ret; 20 for(int i=0;i<2;i++) 21 for(int j=0;j<2;j++) 22 { 23 ret.mat[i][j]=0; 24 for(int k=0;k<2;k++) 25 ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; 26 } 27 return ret; 28 } 29 Matrix pow_M(Matrix a,int n) 30 { 31 Matrix ret; 32 memset(ret.mat,0,sizeof(ret.mat)); 33 for(int i=0;i<2;i++)ret.mat[i][i]=1; 34 Matrix temp=a; 35 while(n) 36 { 37 if(n&1)ret=mul(ret,temp); 38 temp=mul(temp,temp); 39 n>>=1; 40 } 41 return ret; 42 } 43 44 int x[30]; 45 int main() 46 { 47 int n; 48 double p; 49 while(scanf("%d%lf",&n,&p)!=EOF)//POJ上G++要改为cin输入 50 { 51 for(int i=0;i<n;i++) scanf("%d",&x[i]); 52 sort(x,x+n); 53 double ans=1; 54 Matrix tt; 55 tt.mat[0][0]=p; 56 tt.mat[0][1]=1-p; 57 tt.mat[1][0]=1; 58 tt.mat[1][1]=0; 59 Matrix temp; 60 61 temp=pow_M(tt,x[0]-1); 62 ans*=(1-temp.mat[0][0]); 63 64 for(int i=1;i<n;i++){ 65 if(x[i]==x[i-1])continue; 66 temp=pow_M(tt,x[i]-x[i-1]-1); 67 ans*=(1-temp.mat[0][0]); 68 } 69 printf("%.7lf\n",ans);//POJ上G++要改为%.7f 70 } 71 return 0; 72 }