题意：

  一条路上有 $n$ 个地雷，YYF 从位置 $1$ 出发，走一步的概率为 $p$，走两步的概率是 $(1-p)$。求 YYF 能顺利通过这条路的概率。

数据范围： $1\leq n \leq 10$,$0.25\leq p\leq 0.75$，输入的 $n$ 个位置的范围：$[1,1e8]$

分析：

  从前往后推，状态转移方程：$dp[i]=dp[i-1]*p+dp[i-2]*(1-p)$，其中 $dp[1]=1$，有地雷的位置 $dp[i]=0$。如果直接算，必然超时，可以用矩阵快速幂分段优化。

**坑点**：输入的 $n$ 个位置不一定有序。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 int a[15];
 7 double p;
 8 struct matrix
 9 {
10     double mat[3][3];
11     void clc()
12     {
13         for(int i=0;i<3;i++)
14             for(int j=0;j<3;j++)
15                 mat[i][j]=0;
16     }
17     void eye()
18     {
19         for(int i=1;i<=2;i++)
20             mat[i][i]=1;
21     }
22     matrix operator *(const matrix b)const
23     {
24         matrix res;
25         res.clc();
26         for(int i=1;i<=2;i++)
27         {
28             for(int k=1;k<=2;k++)
29             {
30                 for(int j=1;j<=2;j++)
31                     res.mat[i][j]=(res.mat[i][j]+mat[i][k]*b.mat[k][j]);
32             }
33         }
34         return res;
35     }
36 };
37 matrix mpow(matrix a,int b)
38 {
39     matrix res;
40     res.clc();
41     res.eye();
42     while(b)
43     {
44         if(b&1)
45             res=res*a;
46         a=a*a;
47         b>>=1;
48     }
49     return res;
50 }
51 void init(matrix &a)
52 {
53     a.clc();
54     a.mat[1][1]=1;
55 }
56 void init2(matrix &b)
57 {
58     b.clc();
59     b.mat[1][1]=p;
60     b.mat[1][2]=1;
61     b.mat[2][1]=1-p;
62 }
63 int main()
64 {
65     int n,x,last;
66     while(scanf("%d%lf",&n,&p)!=EOF)
67     {
68         for(int i=1;i<=n;i++)
69             scanf("%d",&a[i]);
70         sort(a+1,a+1+n);
71         matrix A,B;
72         init(A);
73         init2(B);
74         bool f=1;
75         last=1;
76         for(int i=1;i<=n;i++)
77         {
78             A=A*mpow(B,a[i]-last);//cout<<"A="<<A.mat[1][2]<<endl;
79             A.mat[1][1]=0;
80             last=a[1];
81         }
82         A=A*B;
83         printf("%.7f\n",A.mat[1][1]);
84     }
85     return 0;
86 }

View Code