一条线段，起点为1，上面有一些点不能走，每次可以以p的概率向右走1步，或以(1-p)的概率向右走2步
求能安全走过整条线段的概率
首先，若1不能走则狗带，若有2个连续的点不能走则狗带
对于所有点都能走的情况，dp[i]表示走到i的概率，dp[i]=dp[i-1]*p+dp[i-1]*(p-2)
可构造矩阵{{p,1-p},{1,0}}，通过矩阵快速幂来优化dp
按不能走的点分段
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int A[15]; 5 struct Matrix{ 6 double a[2][2]; 7 void clear(){ a[0][0]=a[1][1]=1,a[0][1]=a[1][0]=0; } 8 Matrix operator*(Matrix t){ 9 Matrix sum; 10 for(int i=0;i<2;i++) 11 for(int j=0;j<2;j++){ 12 sum.a[i][j]=0; 13 for(int k=0;k<2;k++) 14 sum.a[i][j]+=a[i][k]*t.a[k][j]; 15 } 16 return sum; 17 } 18 }; 19 double qp(Matrix bs,int x){ 20 Matrix sum; sum.clear(); 21 while(x){ 22 if(x&1)sum=sum*bs; 23 bs=bs*bs,x>>=1; 24 } 25 return sum.a[0][0]; 26 } 27 int main(){ 28 int n; double p; 29 while(scanf("%d",&n)!=EOF){ 30 scanf("%lf",&p); 31 for(int i=1;i<=n;i++) 32 scanf("%d",&A[i]); 33 sort(A+1,A+1+n); 34 bool flag=A[1]==1?true:false; 35 for(int i=2;i<=n;i++) 36 if(A[i]==A[i-1]+1)flag=true; 37 double ans; 38 if(A[1]==1)flag=true; 39 if(flag)ans=0; 40 else{ 41 Matrix F; 42 F.a[0][0]=p,F.a[0][1]=1-p; 43 F.a[1][0]=1,F.a[1][1]=0; 44 ans=1; int lst=0; 45 for(int i=1;i<=n;i++){ 46 ans*=(1-p)*qp(F,A[i]-lst-2); 47 lst=A[i]; 48 } 49 } 50 printf("%.7f ",ans);// 51 } 52 return 0; 53 }