Problem B : Power of Matrix
Time limit: 10 seconds
Consider ann-by-nmatrixA. We defineAk=A*A* … *A(ktimes). Here, * denotes the usual matrix multiplication.
You are to write a program that computes the matrixA+A2+A3+ … +Ak.
Example
SupposeA=
. ThenA2=
=
, thus:
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 integersn(≤ 40) andk(≤ 1000000). This is followed bynlines, each containingnnon-negative integers, giving the matrixA.
Input is terminated by a case wheren= 0. This case need NOT be processed.
Output
For each case, your program should compute the matrixA+A2+A3+ … +Ak. Since the values may be very large, you only need to print theirlast digit. Print a blank line after each case.
Sample Input3 20 2 00 0 20 0 00 0Sample Output0 2 40 0 20 0 0Problemsetter: Mak Yan Kei
和POJ3233 – Matrix Power Series一样
// 172 ms #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;int n,m;struct mat{int a[45][45];mat(){memset(a,0,sizeof(a));}};mat A;mat I;mat add(mat m1,mat m2){mat ans;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans.a[i][j]=(m1.a[i][j]+m2.a[i][j])%10;return ans;}mat mul(mat m1,mat m2){mat ans;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(m1.a[i][j])for(int k=1;k<=n;k++)ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k])%10;return ans;}mat quickmul(mat m,int k){mat ans=I;while(k){if(k&1) ans=mul(ans,m);m=mul(m,m);k>>=1;}return ans;}void print(mat m){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)printf("%d%c",m.a[i][j],j==n? '\n':' ');}mat getsum(int k){if(k==1) return A;mat ans=getsum(k/2);if(k&1){mat t=quickmul(A,k/2+1);ans=add(mul(add(I,t),ans),t);}else{mat t=quickmul(A,k/2);ans=mul(add(I,t),ans);}return ans;}int main(){while(scanf("%d%d",&n,&m),n){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;for(int i=1;i<=n;i++) I.a[i][i]=1;mat ans=getsum(m);print(ans);puts("");}return 0;}
，鱼儿爱美，不仅需要鳞甲之美。还需要浮沉活泼之美。
