HDU 4965 Fast Matrix Calculation：矩陣快速冪降維技巧

問題分析

給定 N×K 矩陣 A 和 K×N 矩陣 B (4≤N≤1000, 2≤K≤6)。計算 C = A×B (得 N×N)，再求 D = C^(N²)，最後輸出 D 所有元素模 6 之和。

直接對 N×N 矩陣快速冪：O(N³ log(N²)) ≈ 1000³ × 20 完全不可行。

關鍵洞察：降維到 K×K

觀察 D = C^(N²) = (A×B)^(N²)。利用結合律：

D = A × (B×A)^(N²-1) × B

其中 M = B×A 是 K×K 矩陣 (K≤6)！

• 計算 M = B×A：O(N·K²) ≈ 1000×36
• 快速冪 M^(N²-1)：O(K³ log(N²)) ≈ 6³×20 = 4320
• 計算 D = A × M^(N²-1) × B：O(N²·K) ≈ 10⁶
• 求和模 6

總複雜度主導項為 O(N²·K)，完全可行。

實現細節

• 棧溢出防護：大矩陣遞歸快速冪會爆棧，用迭代或增大棧（#pragma comment(linker, "/STACK:...")）
• 矩陣乘法優化：K≤6 可展開循環，或用靜態陣列避免動態分配
• 模 6 運算：中間結果可能大，用 long long 累積最後取模
• 賦值開銷：N×N 矩陣賦值是 O(N²)，避免不必要的拷貝

偽代碼流程

讀入 N, K
讀入 A[N][K], B[K][N]
M = B × A  // K×K
P = M ^ (N*N - 1)  // 快速冪，K×K
D = A × P × B  // N×N
ans = Σ D[i][j] % 6
輸出 ans

擴展思考

若 K 也很大（如 100），則需考慮 Strassen 算法或特徵值分解。但本題 K≤6 使得降維策略完美生效。這體現了「利用問題結構特殊性（維度非對稱）打破常規複雜度下界」的解題智慧。