POJ 3744 Scout YYF I (概率DP+矩阵快速幂)

题意：小明要从1走过一段直线雷区，给定n个地雷的坐标，他走一步的概率是p，两步的概率为1-p，问你他能安全通过雷区的概率。

析：很明显这是一个概率DP，用d（i）表示到达 i 时他安全的概率，那么d[i] = p * d[i-1] + (1-p) * d[i-2];这个状态转移方程很好理解，

就是说要想到达 i 要么从第 i-1 走一步，要么从 i-2 走两步，最后加起来，然后问题来了，这个数可能达到 1E8，那么时间空间复杂度都受不了，

观察这个状态转移方程，是不是很像Fibnacci数列，所以我们可以用矩阵快速幂来快速计算，如果之前不知道矩阵快速幂的请看：

http://www.cnblogs.com/dwtfukgv/articles/5595078.html

然后我们把这个雷区分成n段，每一段都有一正好有一个雷，也就是x[i-1]+1 ~ x[i]，每一段x[i]都是雷，那么我们只要计算出到在到 i 时，

踩到雷的概率，再用1减去，最后把每一段都乘起来就OK了。再就是要考虑重复的时候，重复是不能算的，还有就是在POJ如果用的scanf要交C++，

不然会WA，或者用cin，这个就可以交G++，我也不知道为什么，第一次交没过，实在没找出错误，我就百度了一下，他们说的。

代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
int x[15];
struct Matrix{
    double a[2][2];
    void init(){
        a[0][0] = a[1][0] = a[0][1] = a[1][1] = 0;
    }
};

Matrix mul(Matrix x, Matrix y){
    Matrix c;   c.init();
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                c.a[i][j] += x.a[i][k] * y.a[k][j];
    return c;
}

Matrix pow(Matrix x, int n){//矩阵快速幂
    Matrix c;  c.init();
    c.a[0][0] = c.a[1][1] = 1;
    while(n){
        if(n & 1)  c = mul(c, x);
        n >>= 1;
        x = mul(x, x);
    }
    return c;
}

int main(){
    int n;  double p;
    while(scanf("%d %lf", &n, &p) == 2){
        for(int i = 1; i <= n; ++i)  scanf("%d", &x[i]);
        x[0] = 0;  sort(x, x+n+1);
        if(1 == x[1]){  printf("%.7lf
", 0.0);  continue; }//要考虑重复的时候

        Matrix m;
        m.a[0][0] = p;   m.a[0][1] = 1;
        m.a[1][0] = 1-p; m.a[1][1] = 0;

        double ans = 1.0;
        for(int i = 1; i <= n; ++i){
            if(x[i] == x[i-1])  continue;
            Matrix temp = pow(m, x[i]-x[i-1]-1);
            ans *= 1 - temp.a[0][0];
        }
        printf("%.7lf
", ans);
    }
    return 0;
}