在一条路上有许多格子，有一个人站在1号格子上，他行走时可以跳一个格子，概率为p，也可以跳两个格子，概率为1-p。其中有N(N<=10)个格子是有地雷的，踩到地雷会丧命。问此人安全走出雷区的概率是多少？格子的坐标范围是[1, 100000000]。
由于坐标的范围很大，因此不可能直接模拟计算。我们注意到，走到第s格的概率是P[s]，那么有公式：
P[s]=(1-p)*P[s-2]+p*P[s-1].
且P[0]=0,P[1]=1。那么使用这个公式可以计算出走到某格的概率。
因此，我们可以分段计算，计算到P[k-1]，其中k为一个地雷。由于k是地雷，因此若要安全走到k+1格，那么p[k+1]=p[k-1]*(1-p)。p[k]=0, 算出p[k+1]后，仿照前面的算法，继续计算下一段路。
计算这个公式可以通过构造矩阵解决。
注意两种概率为0的特殊情况：第一个格子就是地雷，或两个连续的格子都有地雷。
code
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
int n;
double p;
struct Matrix
{
double m[4];
};
Matrix matrix,unit;
Matrix operator*(const Matrix & m1,const Matrix & m2)
{
Matrix res;
res.m[0]=m1.m[0]*m2.m[0]+m1.m[1]*m2.m[2];
res.m[1]=m1.m[0]*m2.m[1]+m1.m[1]*m2.m[3];
res.m[2]=m1.m[2]*m2.m[0]+m1.m[3]*m2.m[2];
res.m[3]=m1.m[2]*m2.m[1]+m1.m[3]*m2.m[3];
return res;
}
Matrix power(int n)
{
Matrix res;
if(n<=0)
{
return unit;
}
if(n==1)
return matrix;
res = power(n/2);
res = res * res;
if(n%2)
res=res*matrix;
return res;
}
void solve()
{
Matrix ans;
double result;
int mine[10];
for(int i=0;i<n;i++)
scanf("%d",&mine[i]);
sort(mine,mine+n);
if(mine[0]==1)
{
printf("%.7lf\n",0.0);
return;
}
for(int i=1;i<n;i++)
if(mine[i]-mine[i-1]==1)
{
printf("%.7lf\n",0.0);
return;
}
result=1.0;
matrix.m[0]=p,matrix.m[1]=1-p,matrix.m[2]=1,matrix.m[3]=0;
unit.m[0]=1,unit.m[1]=0,unit.m[2]=0,unit.m[3]=1;
for(int i=0;i<n;i++)
{
if(i==0)
ans=power(mine[i]-2); /*
安全走到坐标为mine[i]-1处的概率，
当再执行 result=result*ans.m[0]*(1-p); 时，
计算出的就是安全走到坐标是mine[i]+1处的概率。
*/
else ans=power(mine[i]-mine[i-1]-2);/*
从坐标是mine[i-1]+1安全走到mine[i]-1处的概率
当再执行 result=result*ans.m[0]*(1-p); 时，
计算出的就是安全走到坐标是mine[i]+1处的概率。
*/
result=result*ans.m[0]*(1-p);
}
printf("%.7lf\n",result);
}
int main()
{
while(scanf("%d%lf",&n,&p)!=EOF)
{
solve();
}
}