在一條路上有許多格子，有一個人站在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();
}
}