POJ 3744：Scout YYF I - 矩陣快速冪優化概率 DP

問題描述

YYF 從位置 1 出發，每步以概率 p 走 1 步，以概率 1-p 跳 2 步。路徑上有 N ≤ 10 個地雷（位置 ≤ 1e8）。求安全通過所有地雷的概率。

DP 與矩陣加速

設 f[i] 為到達位置 i 的概率。遞推：

f[i] = p * f[i-1] + (1-p) * f[i-2]，f[1]=1, f[0]=0。

這是線性遞推，可用矩陣快速冪計算 f[k]：

[f[i], f[i-1]]^T = M * [f[i-1], f[i-2]]^T，其中 M = [[p, 1-p], [1, 0]]。

f[k] 即 M^(k-1) * [1, 0]^T 的第一分量。

地雷處理

地雷位置排序 pos[1..N]。安全通過概率 = 所有區間「不踩雷」概率的乘積：

• 第一區間 [1, pos[1]-1]：概率 1 - f[pos[1]]（不落在雷上）。
• 後續區間 [pos[i-1]+1, pos[i]-1]：長度 len = pos[i] - pos[i-1] - 1，概率 1 - f[len+1]（從上個雷後一步開始，不落在下個雷上）。

代碼實現

#include <bits/stdc++.h>
using namespace std;

struct Mat {
    double a[2][2];
    Mat(bool ident = false) { memset(a, 0, sizeof(a)); if (ident) a[0][0]=a[1][1]=1; }
};

Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i=0;i<2;++i)
        for (int k=0;k<2;++k)
            for (int j=0;j<2;++j)
                C.a[i][j] += A.a[i][k] * B.a[k][j];
    return C;
}

Mat mpow(Mat base, long long exp) {
    Mat res(true);
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

double prob_reach(long long step, double p) {
    if (step <= 0) return 0;
    Mat M; M.a[0][0]=p; M.a[0][1]=1-p; M.a[1][0]=1; M.a[1][1]=0;
    Mat R = mpow(M, step - 1);
    return R.a[0][0]; // f[step]
}

int main() {
    int N; double p;
    while (scanf("%d%lf", &N, &p) == 2) {
        vector pos(N);
        for (auto &x : pos) scanf("%lld", &x);
        sort(pos.begin(), pos.end());
        bool bad = false;
        for (int i = 0; i < N; ++i)
            if (pos[i] == 1 || (i && pos[i] == pos[i-1])) { bad = true; break; }
        if (bad) { printf("%.7f\n", 0.0); continue; }

        double ans = 1.0;
        ans *= 1 - prob_reach(pos[0], p);
        for (int i = 1; i < N; ++i) {
            long long len = pos[i] - pos[i-1] - 1;
            ans *= 1 - prob_reach(len + 1, p);
        }
        printf("%.7f\n", ans);
    }
    return 0;
}

關鍵點

• 矩陣快速冪將 O(pos) 降為 O(log pos)，應對位置高達 1e8。
• 地雷位置 1 或重複直接輸出 0。
• 概率乘積累積，最終保留 7 位小數。

總結

線性遞推概率 DP + 矩陣快速冪是處理大步數遞推的標準技巧。本題將「避開地雷」轉化為區間內「不落在特定位置」的概率乘積。