FZU 1692 Key Problem：矩陣快速冪優化（循環矩陣降維）

問題描述

n 人圍圈，第 i 人初始有 a_i 蘋果。每輪遊戲：第 i 人增加 R*a_{(i-1+n)%n} + L*a_{(i+1)%n} 個蘋果。進行 m 輪，求最終每人蘋果數模 MOD。n≤100, m≤1e9。

核心建模：線性遞推 → 矩陣乘法

一輪轉移可表示為 n×n 矩陣 T：

T[i][i] = 1
T[i][(i-1+n)%n] = R
T[i][(i+1)%n] = L
其他 = 0

則 m 輪後狀態 A_m = T^m * A_0。直接矩陣快速冪 O(n^3 log m)，n=100 時 100^3 * 30 ≈ 3e7 可能 TLE。

關鍵優化：循環矩陣結構 → O(n² log m)

觀察 T 是**循環矩陣**（每行由前一行循環右移 1 位得到）。循環矩陣乘法可利用 FFT 或結構優化，但這裡用更簡單的「首行推全表」：

1. 只計算 T^m 的**第一行** first_row（向量）。
2. 利用循環性質，第 i 行即 first_row 循環右移 i 位。
3. 向量 × 矩陣乘法 O(n²) 代替矩陣 × 矩陣 O(n³)。

算法流程

1. 構造初始轉移矩陣 T（只需存儲首行或完整矩陣）。
2. 矩陣快速冪計算 T^m，**但乘法優化**：
   • 矩陣 × 向量：O(n²)。
   • 矩陣 × 矩陣：利用循環結構，僅計算結果首行 O(n²)，其餘行由移位得出。
3. 將 T^m 作用於初始向量 A_0 得到結果。

關鍵代碼框架 (C++)

struct Matrix {
    vector> a;
    int n;
    Matrix(int n=0, bool ident=false) : n(n), a(n, vector(n)) {
        if (ident) for (int i=0;i mulVec(const vector& v) const {
        vector res(n);
        for (int i=0;i>= 1;
    }
    return res;
}

複雜度對比

總結

FZU 1692 展示了利用矩陣特殊結構（循環矩陣）將 O(n³) 降為 O(n²) 的經典優化。同類思想適用於「循環卷積、Toeplitz 矩陣、常係數線性遞推」等問題，是矩陣快速冪進階必學技巧。