分析：

dis（k,v1,v2）函数求到当前位置概率为v1,到当前位置之前一步的概率为v2,前进k步到达位置的概率，然后矩阵加速。

代码：

?

//poj 3744
//sep9
#include 
  
   
#include 
   
     using namespace std; int pos[12]; double p,mat[4][4]; double ans[4][4]; void mul1() { double c[4][4]; c[0][1]=c[1][0]=c[0][0]=c[1][1]=0.0; for(int i=0;i<2;++i) for(int j=0;j<2;++j) for(int k=0;k<2;++k) c[i][j]+=ans[i][k]*mat[k][j]; for(int i=0;i<2;++i) for(int j=0;j<2;++j) ans[i][j]=c[i][j]; } void mul2() { double c[4][4]; c[0][1]=c[1][0]=c[0][0]=c[1][1]=0.0; for(int i=0;i<2;++i) for(int j=0;j<2;++j) for(int k=0;k<2;++k) c[i][j]+=mat[i][k]*mat[k][j]; for(int i=0;i<2;++i) for(int j=0;j<2;++j) mat[i][j]=c[i][j]; } double dis(int len,double val,double val1) { mat[1][0]=1.0; mat[0][1]=1-p; mat[0][0]=p; mat[1][1]=0; ans[1][0]=ans[0][1]=0; ans[0][0]=ans[1][1]=1.0; while(len){ if(len&1) mul1(); mul2(); len>>=1; } return ans[0][0]*val+ans[0][1]*val1; } int main() { int n; while(scanf("%d%lf",&n,&p)==2){ pos[0]=0; for(int i=1;i<=n;++i) scanf("%d",&pos[i]); sort(pos+1,pos+1+n); double ans=1,a1=1,a0=0; for(int i=1;i<=n;++i){ if(pos[i]==pos[i-1]) continue; ans=ans-dis(pos[i]-pos[i-1]-1,a1,0); a1=ans; } printf("%.7lf\n",ans); } return 0; } 
   
  

?