切換
舊版
前往
大廳
主題

ZeroJudge - d766: 11149 - Power of Matrix 解題心得

Not In My Back Yard | 2020-08-09 00:00:10 | 巴幣 2 | 人氣 190

題目連結:


題目大意:
輸入有多筆測試資料。每筆測資第一列給定兩正整數 n 、 k (n ≦ 40 、 k ≦ 1000000),代表有一個 n × n 的方陣 A 。接著有 n 列輸入,每列給定 n 個非負整數,代表一個 A 的內容。求 A + A ^ 2 + A ^ 3 + …… + A ^ k 。

因為答案所包含的值可能很大,所以只取每個數字末尾的位數(即個位數)輸出。每筆測資之後多輸出一空白列。詳細見範例輸出。



範例輸入:
3 2
0 2 0
0 0 2
0 0 0
0 0


範例輸出:
0 2 4
0 0 2
0 0 0


解題思維:
因為一次方陣的乘法之時間複雜度為 O(n ^ 3),而有 k 個次方要算。所以暴力去算的話會是 O(k × n ^ 3),絕對會超時。



因此,假設 m = floor(k / 2),其中 floor 函式代表下高斯(對正數來說等於無條件捨去小數點)。我們可以藉由分治法(Divide and Conquer)將原式分群,並依據 k 的奇偶性分為兩種可能:
當 k 為奇數時,可以分為
[A + A ^ 2 + …… + A ^ m] + [A ^ (m + 1) + A ^ (m + 2) + …… + A ^ (2m)] + A ^ k
當 k 為偶數時,可以分為
[A + A ^ 2 + …… + A ^ m] + [A ^ (m + 1) + A ^ (m + 2) + …… + A ^ (2m)]

可以看到右邊的群
[A ^ (m + 1) + A ^ (m + 2) + …… + A ^ (2m)]
的每一項只與左邊的每一項差 A ^ m 倍,所以我們將上式每一項提出 A ^ m 的倍數,變為
[A + A ^ 2 + …… + A ^ m] × A ^ m
將上式與左邊合併即變為
(A + A ^ 2 + …… + A ^ m) × (I + A ^ m)
其中 I 代表為單位方陣。

由此我們就將問題縮減到要求
A + A ^ 2 + …… + A ^ m
當然,如果 k 是奇數的話,還會要多求一項 A ^ k 。

而 m 可以作為上述的新 k 值,然後重複上面的步驟繼續縮減問題。



例如 k = 11 的話,步驟會如下:
令 S1 = A + A ^ 2 + …… + A ^ 11 ,要求 S1 等同於要求
(A + A ^ 2 + …… + A ^ 5) × (I + A ^ 5) + A ^ 11

令 S2 = A + A ^ 2 + …… + A ^ 5 ,要求 S2 等同於要求
(A + A ^ 2) × (I + A ^ 2) + A ^ 5

令 S3 = A + A ^ 2 ,要求 S3 等同於
(A) × (I + A)
而 (A) 已經無法再繼續切下去了,因此可以直接往回推算。所以計算
S3 = A × (I + A)
S2 = (S3) × (I + A ^ 2) + A ^ 5
S1 = (S2) × (I + A ^ 5) + A ^ 11
而 S1 即是我們的所求。

可以看到我們會執行 O(log k) 次的矩陣乘法以及 O(log k) 次的矩陣加法,因此總體的時間複雜度為
O(log k × n ^ 3 + log k × n ^ 2) = O(log k × n ^ 3)
比起暴力法降低了非常大量的運算量。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作