f[i]=f[i-1]*p+f[i-2]*(1-p);
正好可以用矩阵加速。。。。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct matr
{double mat[3][3];friend matr operator *(const matr a,const matr b){matr c;for(int i=1;i<=2;i++){for(int j=1;j<=2;j++){c.mat[i][j]=0;for(int k=1;k<=2;k++){c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];}}}return c;}friend matr operator +(const matr a,const matr b){matr c;for(int i=1;i<=2;i++){for(int j=1;j<=2;j++){c.mat[i][j]=a.mat[i][j]+b.mat[i][j];}}return a;}
}st,gg;
matr mul(matr a,int x)
{matr b;b.mat[1][1]=b.mat[2][2]=1;b.mat[1][2]=b.mat[2][1]=0;while(x){if(x&1)b=b*a;x=x/2;a=a*a;}return b;
}
double get(int x)
{if(x<0)return 0;if(x==0)return 1;matr re;re=mul(gg,x);re=re*st;return re.mat[2][1];
}
int a[111];
int main()
{int n;double p;while(~scanf("%d%lf",&n,&p)){st.mat[1][1]=0; st.mat[1][2]=0;st.mat[2][1]=1; st.mat[2][2]=0;gg.mat[1][1]=0; gg.mat[1][2]=1;gg.mat[2][1]=1-p;gg.mat[2][2]=p;for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);double ans=1.0;a[0]=0;for(int i=1;i<=n;i++){int x=a[i]-a[i-1];ans=ans*get(x-2);ans=ans*(1-p);// cout<<ans<<endl;}printf("%.7f\n",ans);}return 0;
}