【题意】 在一条不满地雷的路上，你现在的起点在1处。在N个点处布有地雷，1<=N<=10。地雷点的坐标范围：[1,100000000].
每次前进p的概率前进一步，1-p的概率前进1-p步。问顺利通过这条路的概率。就是不要走到有地雷的地方。
【分析&解题思路】参考斌神博客，先到概率dp这里入个门。
设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.对于后面的段我们也是一样的假设，这样就乘起来就是答案了。
 
对于每一段的概率的求法可以通过矩阵乘法快速求出来。
【我的AC代码】
 
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
double p;
int x[20];
struct Matrix{
    double a[2][2];
};
Matrix operator *(const Matrix&a,const Matrix&b){
    Matrix c;
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            c.a[i][j]=0;
            for(int k=0; k<2; k++){
                c.a[i][j]+=a.a[i][k]*b.a[k][j];
            }
        }
    }
    return c;
}
Matrix pow(Matrix a,int n){
    Matrix res;
    Matrix temp=a;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<2; i++) res.a[i][i]=1;
    while(n){
        if(n&1) res=res*temp;
        temp=temp*temp;
        n>>=1;
    }
    return res;
}
int main(){
    while(~scanf("%d%lf",&n,&p)){
        for(int i=0; i<n; i++) scanf("%d",&x[i]);
        sort(x,x+n);
        double ans=1.0;
        Matrix bas,now;
        bas.a[0][0]=p,bas.a[0][1]=(1-p);
        bas.a[1][0]=1,bas.a[1][1]=0;
        now=pow(bas,x[0]-1);
        ans*=(1-now.a[0][0]);
        for(int i=1; i<n; i++){
            if(x[i]==x[i-1]) continue;
            now=pow(bas,x[i]-x[i-1]-1);
            ans*=(1-now.a[0][0]);
        }
        printf("%.7f\n",ans);
    }
    return 0;
}