题意：

　　你在一条布满地雷的道路上，开始在坐标1。每次有概率P向前走一步，有概率1-P向前走两步。道中路某几个点上会有地雷，问你安全通过的概率。地雷数N<=10，坐标范围在100000000内。

 

假设dp[i]表示安全走到i点的概率，那么dp[i]=P*dp[i-1]+(1-P)*dp[i-2]。很简单的一个转移，可是偏偏坐标范围太大了。直接递推爆内存，而且肯定也会超时。

我们换一个思路，假设x[i]表示第i个地雷的坐标。对于任何两个地雷x[i]~~x[i-1]+1之间，只会有一个地雷，那就是x[i]。我们安全通过该段的概率等于1 减去猜到x[i]的概率。

也就是说，我们将n个地雷分成n段分别处理。每次都可以得到一个安全通过某一段的概率，最后将这些概率乘起来就是答案了。

可是万一两个地雷之间差的很远怎么办呢？内存和时间还不是一样的不允许？

于是我们用矩阵来优化一下。想想超大fibonacci数的矩阵求法，f[i]=f[i-1]+f[i-2]。f[n]等价于矩阵

| 1 1 |

| 1 0 |

的n次方以后，矩阵的第a[0,0]个元素。

 

同样的，我们为这个dp[i]=P*dp[i-1]+(1-P)*dp[i-2]构造一个矩阵

| P ,1-P |

| 1 , 0   |

那么dp[n]就是该矩阵N次方后的第a[0,0]个元素。

通过二分运算，飞快的就可以求出答案了

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5  6 struct mat 7 { 8     double a[2][2]; 9     mat()10     {11         int i,j;12         for(i=0;i<2;i++)13             for(j=0;j<2;j++)14                 a[i][j]=0;15     }16 };17 18 mat e;19 int n,x[11];20 double p;21 22 mat mul(mat a,mat b)23 {24     int i,j,k;25     mat ans;26     for(i=0;i<2;i++)27         for(j=0;j<2;j++)28             for(k=0;k<2;k++)29                 ans.a[i][j]+=a.a[i][k]*b.a[k][j];30     return ans;31 }32 33 void prit(mat a)34 {35     int i,j;36     for(i=0;i<2;i++)37     {38         for(j=0;j<2;j++)39             printf("%0.2lf ",a.a[i][j]);40         cout<
         
          >1;55     }56     //prit(ans);57     return ans.a[0][0];58 }59 60 int main()61 {62     int i;63     e.a[0][0]=1;e.a[1][0]=0;e.a[1][0]=0;e.a[1][1]=1;64     freopen("D:\\in.txt","r",stdin);65     while(scanf("%d%lf",&n,&p)==2)66     {67         x[0]=0;68         for(i=1;i<=n;i++)69             scanf("%d",&x[i]);70         n++;71         sort(x,x+n);72         mat res;73         double ans=1;74         res.a[0][0]=p;res.a[0][1]=1-p;res.a[1][0]=1;res.a[1][1]=0;75         for(i=1;i