题目大意：n个位置为A[i]的地方有矿，当前位置为1，前进一步的概率为p，两步的概率为1-p，问能穿过矿洞的概率，n<=10,A[i]<=1e8

题目分析：dp[i]为到达位置i的概率，则dp[i]=dp[i-1]*p+dp[i-2]*(1-p)。。数据1e8，矩阵快速幂递推。。。

代码

#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
#include<map>
using namespace std;
struct Q{
    double A[2][2];
}e,x;
Q mul(Q a,Q b){
  Q c;
  int i,j,k;
  for(i=0;i<=1;i++){
      for(j=0;j<=1;j++){
          c.A[i][j]=0;
          for(k=0;k<=1;k++){
            c.A[i][j]+=a.A[i][k]*b.A[k][j];
          }
      }
  }
  return c;
}
Q po(Q a,int b){
  if(b==0) return e;
  Q ans=po(a,b/2);
  ans=mul(ans,ans);
  if(b%2) ans=mul(ans,a);
  return ans;
}
int A[20];
int main(){
    int i,n;
    double p;
    e.A[0][1]=e.A[1][0]=0;  //单位矩阵
    e.A[1][1]=e.A[0][0]=1;
    while(scanf("%d%lf",&n,&p)!=EOF){
        x.A[0][0]=p;
        x.A[0][1]=1-p;    //系数矩阵
        x.A[1][0]=1;
        x.A[1][1]=0;
        for(i=1;i<=n;i++) scanf("%d",&A[i]);
        sort(A+1,A+1+n);
        int a=1,ans=1;
        double k=1;
        for(i=1;i<=n;i++){
            if(a==A[i]){    //当前位置有矿，无法继续前进
                ans=0;
                break;
            }
            if(A[i]==a+1){   //下一个位置有矿，只能跳两步
                a=A[i]+1;
                k*=(1-p);
            }
            else {           //递推到达位置为A[i]-1的概率，然后跳两步
                Q ans=po(x,A[i]-a-2);
                k=ans.A[0][0]*(k*p)+ans.A[0][1]*k;
                a=A[i]+1;
                k*=1-p;
            }
        }
        if(ans==0) printf("0.0000000\n");
        else printf("%.7f\n",k);
    }
    return 0;
}