Consider an n-by-n matrix A. We define Ak = A ∗ A ∗ . . . ∗ A (k times). Here, ∗ denotes the usual matrix multiplication. You are to write a program that computes the matrix A + A2 + A3 + . . . + Ak . Example Suppose A = 0 2 0 0 0 2 0 0 0 . Then A2 = 0 2 0 0 0 2 0 0 0 0 2 0 0 0 2 0 0 0 = 0 0 4 0 0 0 0 0 0 , thus: A + A2 = 0 2 0 0 0 2 0 0 0 + 0 0 4 0 0 2 0 0 0 = 0 2 4 0 0 2 0 0 0 Such computation has various applications. For instance, the above example actually counts all the paths in the following graph: Input Input consists of no more than 20 test cases. The first line for each case contains two positive integers n (≤ 40) and k (≤ 1000000). This is followed by n lines, each containing n non-negative integers, giving the matrix A. Input is terminated by a case where n = 0. This case need NOT be processed. Output For each case, your program should compute the matrix A + A2 + A3 + . . . + Ak . Since the values may be very large, you only need to print their last digit. Print a blank line after each case. Sample Input 3 2 0 2 0 0 0 2 0 0 0 0 0 Sample Output 0 2 4 0 0 2 0 0 0
矩阵快速幂+分治。。。
很巧妙啊 先开始还在想怎么错位相减。。。
具体细节不讲了 代码里都有 这道题给我们的启示是碰见这种连续幂相加的东西要想分治。。。
先开始t了半天，结果写成暴力了。。。
#include<bits/stdc++.h> using namespace std; const int N = 41; struct mat { int a[N][N]; } A; int n, k; mat operator * (mat A, mat B) { mat ret; memset(ret.a, 0, sizeof(ret.a)); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) for(int k = 1; k <= n; ++k) ret.a[i][j] = (ret.a[i][j] + A.a[i][k] % 10 * B.a[k][j] % 10) % 10; return ret; } mat power(mat x, int t) { mat ret; memset(ret.a, 0, sizeof(ret.a)); for(int i = 1; i <= n; ++i) ret.a[i][i] = 1; for(; t; t >>= 1, x = x * x) if(t & 1) ret = ret * x; return ret; } mat operator + (mat A, mat B) { for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) A.a[i][j] = (A.a[i][j] + B.a[i][j]) % 10; return A; } mat solve(int t) { if(t == 1) return A; mat x = solve(t / 2), ret = x, B = power(A, t / 2); if(t & 1) return x + (x + B * A) * B; else return x + x * B; } int main() { while(scanf("%d%d", &n, &k)) { if(n == 0) break; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d", &A.a[i][j]), A.a[i][j] %= 10; mat x = solve(k); for(int i = 1; i <= n; ++i) { for(int j = 1; j < n; ++j) printf("%d ", x.a[i][j]); printf("%d ", x.a[i][n]); } puts(""); } return 0; }