HDU 1575(数論、行列乗算+べき乗を求める)


Tr A
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 361    Accepted Submission(s): 282
Problem Description
Aが1つの行列である場合、Tr AはAの跡(主対角線上の各項目の和)を表し、Tr(A^k)%9973が要求される.
 
 
Input
データの最初の行はTであり、Tグループのデータがあることを示す.
各データ群の最初の行にはn(2<=n<=10)とk(2<=k<10^9)の2つのデータがある.次にn行があり、各行にn個のデータがあり、各データの範囲は[0,9]であり、行列Aの内容を表す.
 
 
Output
各データセットに対応してTr(A^k)%9973を出力する.
 
 
Sample Input

   
   
   
   
2 2 2 1 0 0 1 3 99999999 1 2 3 4 5 6 7 8 9

 
 
Sample Output

   
   
   
   
2 2686
#include <iostream> using namespace std; #define N 10 #define ll __int64 struct Mat { int martix[N][N]; }; Mat q,res,tp; int n,mod; Mat Martix_Mul(Mat a,Mat b) { Mat c; int i,j,k; for (i=0;i<n;i++) { for(j=0;j<n;j++) { c.martix[i][j]=0; for (k=0;k<n;k++) { c.martix[i][j]+=(a.martix[i][k]*b.martix[k][j])%mod; c.martix[i][j]%=mod; } } } return c; } void er_fun(ll x) { tp=q; q=res; while (x) { if(x&1) q=Martix_Mul(q,tp); tp=Martix_Mul(tp,tp); x>>=1; } } int main() { int t,i,j; ll k,sum; mod=9973; for(i=0;i<N;i++) { for (j=0;j<N;j++) { if(i==j) res.martix[i][j]=1; else res.martix[i][j]=0; } } while (scanf("%d",&t)!=EOF) { while(t--) { sum=0; scanf("%d%I64d",&n,&k); for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&q.martix[i][j]); } } er_fun(k); for(i=0;i<n;i++) { for (j=0;j<n;j++) { if(i==j) sum+=q.martix[i][j]; } } printf("%I64d/n",sum%mod); } } return 0; }