ZOJ 3772 Calculate the Function 矩陣線段樹 區間遞推查詢

問題

數列 A[1..N]，查詢 F(L,R) 定義為：

• F(L) = A[L], F(L+1) = A[L+1]
• F(x) = F(x-1) + F(x-2) * A[x] (x ≥ L+2)
• 求 F(R) mod 1e9+7

N, M ≤ 100,000，多測試案例。

矩陣形式化遞推

設狀態向量 [F(x), F(x-1)]^T，則：

[F(x)  ]   [1  A[x]] [F(x-1)  ]
[F(x-1)] = [1   0  ] [F(x-2)  ]

區間 [L+2, R] 的轉移矩陣為 M_R * M_{R-1} * ... * M_{L+2}（注意順序：右乘左）。

線段樹維護區間矩陣乘積

• 葉節點存 M_i = [[1, A[i]], [1, 0]]
• 內部節點存左右子節點矩陣乘積：tree[u] = tree[rc] * tree[lc]（右子樹矩陣在左）
• 查詢區間 [l, r] 返回對應乘積矩陣

答案計算

if (R - L <= 1) return A[R];
Matrix M = query(L+2, R);
long long ans = (M.a[0][0] * A[L+1] + M.a[0][1] * A[L]) % MOD;

關鍵代碼

struct Matrix {
    long long a[2][2];
    Matrix(long long x=0) { a[0][0]=a[1][0]=1; a[0][1]=x; a[1][1]=0; }
};

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

void build(int u, int l, int r) {
    if (l==r) { tree[u]=Matrix(A[l]); return; }
    int mid=(l+r)>>1;
    build(u<<1,l,mid); build(u<<1|1,mid+1,r);
    tree[u]=mul(tree[u<<1|1], tree[u<<1]); // 右乘左
}

Matrix query(int u, int l, int r, int ql, int qr) {
    if (ql<=l && r<=qr) return tree[u];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(u<<1,l,mid,ql,qr);
    if (ql>mid) return query(u<<1|1,mid+1,r,ql,qr);
    return mul(query(u<<1|1,mid+1,r,ql,qr), query(u<<1,l,mid,ql,qr));
}

複雜度

• 構建：O(N)
• 單次查詢：O(log N)
• 總體：O((N+M) log N)，滿足 1e5 限制

關鍵細節

• 矩陣乘法順序：右區間矩陣 × 左區間矩陣（因向量右乘）
• 基礎情況 R-L≤1 直接返回 A[R]
• 模 1e9+7 運算防溢出