Tr ATime Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3169Accepted Submission(s): 2367
Problem Description
A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），，现要求Tr(A^k)%9973。
Input
数据的第一行是一个T，表示有T组数据。每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。
Output
对应每组数据，输出Tr(A^k)%9973。
Sample Input
22 21 00 13 999999991 2 34 5 67 8 9
Sample Output
22686
Author
xhd
矩阵快速幂第一发，以前碰到好几次矩阵快速幂的题，因为这样那样的原因一直没有学，今天拿出来学一下，其实就和快速幂取余的思想差不多。get√
#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <algorithm>#include <set>#include <map>#include <queue>using namespace std;const int inf=0x3f3f3f3f;const int mod=9973;int n;struct node {int mp[20][20];} init,res;struct node Mult(struct node x, struct node y)// 矩阵相乘{struct node tmp;int i,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++) {tmp.mp[i][j]=0;for(k=0;k<n;k++)tmp.mp[i][j]=(tmp.mp[i][j]+x.mp[i][k]*y.mp[k][j])%mod;}return tmp;};struct node expo(struct node x, int k)//矩阵快速幂{struct node tmp;int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++) {if(i==j)tmp.mp[i][j]=1;elsetmp.mp[i][j]=0;}while(k) {if(k&1) tmp=Mult(tmp,x);x=Mult(x,x);k>>=1;}return tmp;};int main(){int T,i,j,k;int ans;scanf("%d",&T);while(T–) {scanf("%d %d",&n,&k);for(i=0; i<n; i++)for(j=0; j<n; j++)scanf("%d",&init.mp[i][j]);res=expo(init,k);ans=0;for(i=0; i<n; i++)ans=(ans+res.mp[i][i])%mod;printf("%d\n",ans);}return 0;}
却又小到连一粒嫉妒的沙石也不能容纳
