POJ 3744-Scout YYF I【概率DP+矩阵快速幂】-蒲公英云

POJ 3744-Scout YYF I【概率DP+矩阵快速幂】

题意：有n个地方有地雷，给出来你下标，对于每个位置i, 你走到i+1的概率是p，走到i+2的概率是1-p，问你不被地雷炸的概率。

思路：这题转移方程很好想，就是f[i] = p * f[i - 1] + (1 - p) * f[i - 2], f[1] = 1.

但是由于n范围很大，我们考虑用矩阵快速幂来优化，我们将地雷按照下标分段，只要经过这一段我们不被地雷炸就行了，

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
const int maxn = 1e2 + 10;
struct mat
{
    static const int N = 2;
    double M[N][N];
    mat(ll v = 0)
    {
        memset(M, 0, sizeof(M));
        if(v) //可以初始化为单位矩阵
            for(int i = 0; i < N; ++i)
                M[i][i] = v;
    }
    mat operator * (const mat &b)
    {
        mat c;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                for(int k = 0; k < N; ++k)
                    c.M[i][j] = c.M[i][j] + M[i][k] * b.M[k][j];
        return c;
    }
    friend mat operator ^ (mat a, ll n)
    {
        mat res(1);
        while(n)
        {
            if(n & 1)
                res = res * a;
            a = a * a;
            n >>= 1;
        }
        return res;
    }
};
int x[maxn];
int main()
{
    int n; double p;
    while(~scanf("%d%lf", &n, &p))
    {
        mat a, b;
        b.M[0][0] = p, b.M[0][1] = 1;
        b.M[1][0] = 1 - p, b.M[1][1] = 0;
        double ans = 1;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &x[i]);
        }
        sort(x + 1, x + n + 1);
        a = b ^ (x[1] - 1);
        ans *= (1 - a.M[0][0]);
        for(int i = 2; i <= n; ++i)
        {
            a = b ^ (x[i] - x[i - 1] - 1);
            ans *= (1 - a.M[0][0]);
        }
        printf("%.7f\n", ans);
    }
    return 0;
}