题目大意：有n颗地雷分布在一条直线上，有个人的起始位置在1，他每次前进1步的概率为p，前进两步的概率为1-p，问他不碰到地雷的概率。
题目分析：定义状态dp(i)表示到了dp(i)的概率，则状态转移方程为dp(i)=p*dp(i-1)+(1-p)*dp(i-2)。要想安全通过x(i)到达x(i)+1只能由x(i)-1走两步，所以，可以将整条直线分成n段，那么从x(i-1)+1安全通过第 i 颗地雷概率为1-p(到达x(i))。坐标之间的距离又很大，所以可以用矩阵二分幂优化。
代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; struct Matrix
{
int r,c;
double m[2][2];
}; int x[12];
double p; Matrix multiply(Matrix a,Matrix b)
{
Matrix res;
res.r=a.r;
res.c=b.c;
for(int i=0;i<res.r;++i){
for(int j=0;j<res.c;++j){
res.m[i][j]=0;
for(int k=0;k<a.c;++k)
res.m[i][j]+=a.m[i][k]*b.m[k][j];
}
}
return res;
} Matrix myPow(Matrix a,int n)
{
if(n==0){
a.m[0][0]=a.m[1][1]=1;
a.m[0][1]=a.m[1][0]=0;
return a;
}else{
Matrix res=myPow(a,n>>1);
res=multiply(res,res);
if(n&1)
res=multiply(res,a);
return res;
}
} double solve()
{
Matrix mat;
mat.r=mat.c=2;
mat.m[0][0]=p,mat.m[0][1]=1-p;
mat.m[1][0]=1,mat.m[1][1]=0;
sort(x+1,x+x[0]+1);
Matrix temp=myPow(mat,x[1]-1);
double ans=1-temp.m[0][0];///ans为安全通过第i颗地雷的概率。
for(int i=2;i<=x[0];++i){
if(x[i]==x[i-1]) continue;
temp=myPow(mat,x[i]-x[i-1]-1);
ans*=(1-temp.m[0][0]);
}
return ans;
} int main()
{
while(~scanf("%d",&x[0]))
{
scanf("%lf",&p);
for(int i=1;i<=x[0];++i)
scanf("%d",x+i);
printf("%.7lf\n",solve());
}
return 0;
}