POJ 3744 Scout YYF I：概率 DP + 矩陣快速冪（斐波那契型遞推）

問題轉化

YYF 沿數軸移動，某些位置有「陷阱」。從 0 出發，每步 +1 或 +2（概率 p, 1-p）。求到達終點不踩陷阱的概率。
等價於：在無陷阱區間長度 L 內，從左端點走到右端點的概率。

遞推關係

設 f[i] = 從位置 i 走到區間右端點的概率。
f[i] = p·f[i+1] + (1−p)·f[i+2]。
邊界：f[R] = 1, f[R+1] = 0。
這是線性遞推，可用 2×2 矩陣快速冪加速。
轉移矩陣：
[ f[i] ] = [ p 1−p ] [ f[i+1] ]
[ f[i+1] ] [ 1 0 ] [ f[i+2] ]

算法流程

1. 讀入陷阱位置，排序，添加虛擬邊界 0 和終點+1。
2. 對每個無陷阱區間 (pos[i-1], pos[i])，長度 L = pos[i] − pos[i-1] − 1。
   計算從區間左端點走 L 步到達右端點的概率 prob。
   總體生存概率乘以 prob。
3. 矩陣快速冪計算 prob：初始向量 [1, 0]^T（對應 f[R]=1, f[R+1]=0），左乘矩陣 L 次，取第一分量。

代碼核心

struct Mat { double a[2][2]; };
Mat mul(Mat A, Mat B) {
    Mat C; memset(C.a, 0, sizeof(C.a));
    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; memset(res.a, 0, sizeof(res.a));
    res.a[0][0]=res.a[1][1]=1;
    while (exp) {
        if (exp&1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}
double calc_interval(long long len, double p) {
    if (len <= 0) return 1;
    Mat trans = {{{p, 1-p}, {1, 0}}};
    Mat m = mpow(trans, len);
    return m.a[0][0]; // f[0] = m[0][0]*1 + m[0][1]*0
}

複雜度

O(K log L)，K 為陷阱數，L 為區間長度，極快。