HDU 2276 Kiki & Little Kiki 2：位運算優化矩陣快速冪求最小逆序

HDU 2276 Kiki & Little Kiki 2：位運算優化矩陣快速冪求最小逆序

環狀燈序列，每秒第 i 盞燈根據左鄰燈狀態翻轉：左鄰亮則翻轉，否則不變。求 m 秒後狀態（n ≤ 1e5, m ≤ 1e9）。

狀態轉移分析

設 a_i 為當前狀態，L_i 為左鄰狀態。真值表：

發現規律：新狀態 = (原狀態 + 左鄰) & 1（等價於 XOR，但矩陣乘法需要加法）。

矩陣構造

狀態向量 V = [a1, a2, ..., an]^T。轉移矩陣 T 為 n×n：

T = | 1 0 0 ... 0 1 |  // a1' = a1 + an
    | 1 1 0 ... 0 0 |  // a2' = a2 + a1
    | 0 1 1 ... 0 0 |  // a3' = a3 + a2
    | ...           |
    | 0 0 0 ... 1 1 |  // an' = an + a(n-1)

則 V(m) = T^m * V(0)。所有運算模 2。

位運算優化矩陣乘法

模 2 下：加法 = XOR (^)，乘法 = AND (&)。
將矩陣每行壓縮為 unsigned long long 位掩碼（n ≤ 64 時），或用 bitset/數組模擬。代碼中用 int 數組但利用位運算加速：

Mat operator*(Mat a, Mat b) {
    Mat c(a.n);
    for (int i = 0; i < a.n; i++)
        for (int j = 0; j < a.n; j++) {
            c.v[i][j] = 0;
            for (int k = 0; k < a.n; k++)
                c.v[i][j] ^= (a.v[i][k] & b.v[k][j]); // 關鍵：^= &
        }
    return c;
}

快速冪模板不變，僅乘法內核替換。最終 ans = max(0, 初始逆序數 - k) 邏輯同 HDU 4911。

完整代碼結構

struct Mat {
    int n; int v[101][101];
    Mat(int _n=101):n(_n) { memset(v,0,sizeof(v)); }
    void eye() { for(int i=0;i>=1; }
    return c;
}
int main() {
    while(~scanf("%d%d",&n,&m)){
        // 讀初始狀態填入向量 b
        // 構造矩陣 a
        Mat c = a ^ m;
        c = c * b;
        // 輸出 c.v[i][0]
    }
}

關鍵洞察

• 布爾矩陣乘法可用位運算加速，O(n^3/64) 甚至 O(n^3/word_size)。
• 環狀邊界條件體現在矩陣第一行最後一列與最後一行第一列為 1。
• 模 2 線性系統求解是矩陣快速冪的經典應用場景。