poj3744 概率dp+矩阵乘法_概率方法设计计算方法ab=c,均为方阵,且n>100000000

题目大意

在一条路上有n个地雷，有个SB人按照心情走在这条路上，往前走1步的概率是p，往前走2步的概率是(1-p)，求他活着走过这条路的概率。

分析

很容易想到一种dp方程：f[i]=p*f[i-1]+(1-p)*f[i-2];
然而一看范围：[1, 100000000]
怎么可能不超时呢……
然后可以这么想：只要避开了最后一个地雷不就安全了吗？我们把路分成n段，分别是1～地雷1位置，地雷1位置+1～地雷2位置，地雷2位置+1～地雷3位置，每次的目标是避开每段最后那个地雷。
然后我们可以用矩阵快速幂来加速，因为显然：

$$\left\{ \begin{matrix} f[i]\\ f[i-1] \end{matrix} \right\} = \left\{ \begin{matrix} p & 1-p \\ 1 & 0 \end{matrix} \right\} * \left\{ \begin{matrix} f[i-1]\\ f[i-2] \end{matrix} \right\}$$
然后初始值f[1]=1,f[2]=p;所以进行当前这一段长度-1的矩阵乘法后，处在左上角的那个数就是踩到地雷的概率了。
不过这个概率是建立在f[1]=1的基础上的，而对于不是第一段的段，最初的f值不一定是1，不过也没关系，显然那个值就是避开了前一段地雷，活着来到这一段的值啦。所以每次矩阵快速幂后进行ans=ans*(1-mat[0][0]);的操作即可！
如果有不懂的地方看看代码可能就懂了呢。

代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int n;double p;
int a[12];
struct jz{double mat[2][2];};
jz mul(jz x,jz y){//矩阵乘法
    int i,j,k;
    jz re;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++){
        re.mat[i][j]=0;
        for(k=0;k<2;k++)re.mat[i][j]+=x.mat[i][k]*y.mat[k][j];
    }
    return re;
}
jz pow(jz aa,int n){//矩阵快速幂
    jz ans;
    memset(ans.mat,0,sizeof(ans.mat));
    ans.mat[0][0]=ans.mat[1][1]=1;
    while(n){
        if(n&1){ans=mul(ans,aa);}
        aa=mul(aa,aa);
        n>>=1;
    }
    return ans;
}
int main()
{
    int i;
    while(scanf("%d%lf",&n,&p)!=EOF){
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+1+n);double ans=1;
        jz gg,tmp;
        gg.mat[0][0]=p;gg.mat[0][1]=1.0-p;
        gg.mat[1][0]=1.0;gg.mat[1][1]=0;
        tmp=pow(gg,a[1]-1);
        ans*=(1-tmp.mat[0][0]);
        for(i=2;i<=n;i++){
            if(a[i-1]==a[i])continue;
            tmp=pow(gg,a[i]-a[i-1]-1);
            ans*=(1-tmp.mat[0][0]);//活着离开这一段的概率
        }
        printf("%.7f\n",ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52