题意：n个雷，分别在a[1]…a[n] ，走一步概率为 p ，走两步概率为 1-p ，一开始在 1 号位置，问安全到达终点的概率。
思路：
将整个过程划分成阶段处理：
1 ~ a[1]
a[1]+1 ~ a[2]
…………
a[n-1]+1 ~ a[n]
那么只要求出每次踩到雷的概率，求反面，再把所有阶段结果连乘就可以了。
ans[i]表示踩中i的概率，，那么可推倒出ans[i]=p*ans[i-1]+(1-p)*ans[i-2]
因为直接暴力求解超时，构造矩阵
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<string>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#define INF 0x7fffffff#define SUP 0x80000000#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int N=100007;struct Matrix{double mat[2][2];};Matrix mul(Matrix a,Matrix b) //矩阵乘法{Matrix ret;for(int i=0;i<2;i++){for(int j=0;j<2;j++){ret.mat[i][j]=0;for(int k=0;k<2;k++)ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j];}}return ret;}Matrix qpow(Matrix a,int n) //矩阵快速幂{Matrix ret;mem(ret.mat,0);for(int i=0;i<2;i++) ret.mat[i][i]=1;Matrix tmp=a;while(n){if(n&1) ret=mul(ret,tmp);n>>=1;tmp=mul(tmp,tmp);}return ret;}int a[20];int main(){int n;double p;while(scanf("%d%lf",&n,&p)==2){for(int i=1;i<=n;i++)scanf("%d",a+i);sort(a+1,a+1+n);double ans=1;Matrix fir,tmp;fir.mat[0][0]=p;fir.mat[0][1]=1-p;fir.mat[1][0]=1;fir.mat[1][1]=0;tmp=qpow(fir,a[1]-1);ans*=(1-tmp.mat[0][0]);for(int i=2;i<=n;i++){if(a[i]==a[i-1]) continue;tmp=qpow(fir,a[i]-a[i-1]-1);ans*=(1-tmp.mat[0][0]);}printf("%.7f\n",ans);}return 0;}
任何的限制，都是从自己的内心开始的。
