2011-06-16 18:13:29Morris
d766. 11149 - Power of Matrix
內容 ：
考慮一個 ｎ * ｎ 矩陣 A ：我們確定的Ak = A * A * ... * A（k次）。在這裡，’*’ 表示通常的矩陣乘法。
你要編寫一個程式，計算矩陣A + A2 + A3 + ... + Ak.
Example
設 A = 
. 然後 A2 = = 
, 因此:
這樣的計算有多種應用。例如，上面的例子，其實就是下面的路徑圖：
輸入說明 ：
輸入由不超過 20測試資料。每個測試資料第一行包含兩個正整數 n（≤40）和k（≤1000000）。其次是N行，每一個包含N個非負整數，給矩陣 A
輸入是終止條件：n = 0。這種情況下不需要進行處理。
輸出說明 ：
對於每個測試資料, 你的程式只要計算A + A2 + A3 + ... + Ak . 算出來的答案可能很大, 你只需要輸出最後一個數字就好. 輸出一行空白列在每筆測試資料後。
範例輸入 ：
3 20 2 00 0 20 0 00 0
範例輸出 ：
0 2 40 0 20 0 0
提示 ：
出處 ：
11149 - Power of Matrix (管理：asas)
作法 : 數學 & 矩陣乘法 & D&C
A + A2 + A3 + ... + Ak.
if(k&1)/*奇數*/
A + A2 + A3 + ... + Ak = (A + A2 + A3 + ... + Ak/2)*(I + Ak/2 ) + Ak
else
A + A2 + A3 + ... + Ak = (A + A2 + A3 + ... + Ak/2)*(I + Ak/2 )
I : 單位矩陣 k/2 => 取整數
遞迴下去，O(logk)
計算矩陣是O(N^3 logk)
作法 : 數學 & 矩陣乘法 & D&C
A + A2 + A3 + ... + Ak.
if(k&1)/*奇數*/
A + A2 + A3 + ... + Ak = (A + A2 + A3 + ... + Ak/2)*(I + Ak/2 ) + Ak
else
A + A2 + A3 + ... + Ak = (A + A2 + A3 + ... + Ak/2)*(I + Ak/2 )
I : 單位矩陣 k/2 => 取整數
遞迴下去，O(logk)
計算矩陣是O(N^3 logk)
#include<stdio.h>
typedef struct {
int t[40][40];
}Matrix;
Matrix A, In, init, Ans;
Matrix mult(Matrix x, Matrix y, int n) {
Matrix t = init;
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
for(k = 0; k < n; k++) {
t.t[i][k] += x.t[i][j]*y.t[j][k];
}
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
t.t[i][j] %= 10;
return t;
}
Matrix add(Matrix x, Matrix y, int n) {
int i, j;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
x.t[i][j] = (x.t[i][j] + y.t[i][j]) % 10;
return x;
}
Matrix Calu_Ak(int k, int n) {
Matrix x = In, y = A;
while(k) {
if(k&1) x = mult(x, y, n);
y = mult(y, y, n);
k /= 2;
}
return x;
}
Matrix Calu_total(int n, int k) {
if(k == 0) return init;
if(k&1) {
return add(mult(Calu_total(n, k/2), add(In, Calu_Ak(k/2, n), n), n), Calu_Ak(k, n), n);
}
else {
return mult(Calu_total(n, k/2), add(In, Calu_Ak(k/2, n), n), n);
}
}
main() {
int n, a, b, k, x, y, s;
while(scanf("%d %d", &n, &k) == 2 && n) {
for(a = 0; a < n; a++)
for(b = 0; b < n; b++)
A.t[a][b] = 0, In.t[a][b] = 0,
init.t[a][b] = 0;
for(a = 0; a < n; a++) In.t[a][a] = 1;
for(a = 0; a < n; a++)
for(b = 0; b < n; b++)
scanf("%d", &A.t[a][b]), A.t[a][b] %= 10;
Ans = Calu_total(n, k);
for(a = 0; a < n; a++, puts(""))
for(b = 0; b < n; b++) {
printf("%d", Ans.t[a][b]);
if(b != n-1)
printf(" ");
}
puts("");
}
return 0;
}