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

迈不过友情╰ 2023-06-02 15:56 93阅读 0赞

题意：有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;
    }