POJ 3744 Scout YYF I（矩阵快速幂优化+概率dp）

题意：

现在有个屌丝要穿越一个雷区，雷分布在一条直线上，但是分布的范围很大，现在这个屌丝从1出发，p的概率往前走1步，1-p的概率往前走2步，求最后顺利通过雷区的概率。

思路：

首先很容易能得到一个递推式：$dp[i]=p*dp[i-1]+(1-p)*dp[i-2]$。但是直接递推肯定不行，然后我们发现这个很容易构造出矩阵来，但是这样还是太慢。

接下来讲一下如何优化，对于第i个雷，它的坐标为x[i]，那么那顺利通过它的话，只能在x[i]-1的位置走2步。

观察上图，可以发现每次起点就相当于是雷后面的一个格子，这样的话我们就可以分块处理（有多少雷就分多少块），先计算出起点到雷的概率y，那么1-y就是顺利通过这块的概率。最后乘法原理乘起来即可。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 const int INF = 0x3f3f3f3f;
14 const int maxn=100000+10;
15 
16 int n;
17 double p, ans;
18 int x[15];
19 
20 struct Matrix
21 {
22     double mat[2][2];
23     Matrix()
24     {
25         for(int i=0;i<2;i++)
26         for(int j=0;j<2;j++)
27             mat[i][j]=0;
28     }
29     Matrix operator* (const Matrix& b) const
30     {
31         Matrix c;
32         for(int i=0;i<2;i++)
33         for(int j=0;j<2;j++)
34         for(int k=0;k<2;k++)
35             c.mat[i][j]+=mat[i][k]*b.mat[k][j];
36         return c;
37     }
38 }base;
39 
40 Matrix q_pow(Matrix base, int n)
41 {
42     Matrix res;
43     res.mat[0][0]=res.mat[1][1]=1;
44     while(n)
45     {
46         if(n&1) res=res*base;
47         base=base*base;
48         n>>=1;
49     }
50     return res;
51 }
52 
53 int main()
54 {
55     //freopen("in.txt","r",stdin);
56     while(~scanf("%d%lf",&n,&p))
57     {
58         for(int i=1;i<=n;i++)  scanf("%d",&x[i]);
59         sort(x+1,x+n+1);
60         base.mat[0][0]=p;
61         base.mat[0][1]=1-p;
62         base.mat[1][0]=1;
63         base.mat[1][1]=0;
64         ans=1;
65         Matrix tmp=q_pow(base, x[1]-1);
66         ans*=(1-tmp.mat[0][0]);
67         for(int i=2;i<=n;i++)
68         {
69             if(x[i]==x[i-1])  continue;
70             tmp=q_pow(base, x[i]-x[i-1]-1);
71             ans*=(1-tmp.mat[0][0]);
72         }
73         printf("%.7f
",ans);
74     }
75     return 0;
76 }