POJ 3744 Scout YYF I：概率 DP + 矩陣快速冪優化線性遞推

POJ 3744「Scout YYF I」：一維隨機游走，位置 i 到 i+1 概率 p，到 i+2 概率 1-p。某些位置有陷阱（踩中失敗）。求從 0 走到 n 不踩陷阱的概率。n 極大 (10⁹)，陷阱數 m ≤ 10。本文解析區間矩陣快速冪優化 DP。

遞推關係

設 dp[i] = 從 0 安全到達 i 的概率。
dp[i] = p * dp[i-1] + (1-p) * dp[i-2] (i ≥ 2)
初始：dp[0]=1, dp[1]=p (假設 1 無陷阱)。

矩陣形式

[dp[i], dp[i-1]]^T = M * [dp[i-1], dp[i-2]]^T
M = [[p, 1-p], [1, 0]]

區間 [L, R] 無陷阱時：[dp[R], dp[R-1]]^T = M^(R-L) * [dp[L], dp[L-1]]^T

算法流程

1. 讀入陷阱位置，排序，加入 0 和 n+1 作為邊界。
2. 若相鄰陷阱距離為 1 → 必經陷阱，答案 0。
3. 初始 dp[0]=1, dp[1]=p (若 1 是陷阱則 dp[1]=0)。
4. 遍歷陷阱間隔：
5. 設當前安全區間為 [a, b]，下一陷阱在 c = b+1。
6. 用矩陣快速冪計算 dp[b]、dp[b-1]。
7. 踩陷阱 c 概率 = p*dp[b] + (1-p)*dp[b-1]，安全通過 c 需跳過 → dp[c+1] = (1-p)*dp[b] (從 b 跳 2 步)。
8. 最終答案為 dp[n] (或最後安全位置的概率)。

關鍵代碼片段（C++）

struct Mat {
    double a[2][2];
    Mat() { memset(a, 0, sizeof(a)); }
    static Mat identity() { Mat I; I.a[0][0]=I.a[1][1]=1; return I; }
};

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 = Mat::identity();
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

int main() {
    int n, m; double p;
    while (scanf("%d%lf", &n, &p) == 2) {
        vector trap(m);
        for (int i=0;i 0) {
                Mat Mp = mpow(M, len);
                double ndp0 = Mp.a[0][0]*dp0 + Mp.a[0][1]*dp1;
                double ndp1 = Mp.a[1][0]*dp0 + Mp.a[1][1]*dp1;
                dp0 = ndp0; dp1 = ndp1;
            }
            // 經過陷阱 t: 從 t-1 跳1步(p) 或 t-2 跳2步(1-p) 會踩中
            // 安全到達 t+1: 必須從 t-1 跳2步 (1-p)*dp[t-1]
            double safe = (1-p) * dp1; // dp1 是 dp[t-1]
            dp0 = dp1; // dp[t] = 0 (陷阱)
            dp1 = safe; // dp[t+1]
            prev = t;
        }
        // 最後一段到 n
        int len = n - prev - 1;
        if (len > 0) {
            Mat Mp = mpow(M, len);
            double ndp0 = Mp.a[0][0]*dp0 + Mp.a[0][1]*dp1;
            dp0 = ndp0;
        }
        printf("%.7lf\n", dp0);
    }
    return 0;
}

複雜度

• 矩陣乘法 O(2³) = O(1)。
• 快速冪 O(log 區間長度)。
• 陷阱數 m ≤ 10，總時間 O(m log n) 極快。

關鍵細節

1. 陷阱處理邏輯：踩中即失敗，只計算「安全通過」的概率分支。
2. 初始條件：dp[0]=1，dp[1]=p (從 0 跳 1 步)。若 1 是陷阱則 dp[1]=0。
3. 區間長度計算：仔細處理陷阱前後的安全段長度。
4. 輸出精度：%.7lf。

總結

本題是「線性遞推 + 稀疏障礙 + 巨大步數」的標準模式：矩陣快速冪跳過無障礙區間，逐個處理障礙點。核心技巧：

1. 將遞推轉化為矩陣乘法。
2. 利用結合律 M^(a+b) = M^a * M^b 分段計算。
3. 障礙點作為「邊界條件重置點」，手動處理其概率轉移。

此模板適用於所有「線性遞推 + 少量特殊位置修正 + 大 n」問題。