HDU 1575

Tr  A

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

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

2　

2　2 　

1　0 　

0　1

3　99999999

1　2　3

4　5　6

7　8　9

 

Sample Output

2 　2686

 

 

 

 

 

分析：根据题意，用矩阵快速幂求解。

 

 

 

 

 

 

 

代码如下： 

 

#include <iostream> 
#include<cstdio>  
#include<cstring> 


 
using namespace std;  
const int maxn = 15;  
const int mod=9973;  
int res[maxn][maxn];  
int n;  
void mul(int x[][15],int y[][15],int z[][15])
{  
    int temp[15][15];  
	memset(temp,0,sizeof(temp));  
    for(int i=0;i<n;i++)  
      for(int j=0;j<n;j++)  
        for(int k=0;k<n;k++)
           temp[i][j]=(temp[i][j]+x[i][k]*y[k][j])%mod;  
        memcpy(z,temp,sizeof(temp));  
}  
void pow(int a[][15],int k)
{  
     while(k)
	 {  
         if(k%2==1)
             mul(res,a,res);    
         mul(a,a,a);  
         k/=2;    
     }  
}  
int main()
{  
    int t,k;  
    int a[maxn][maxn];  
    scanf("%d",&t);  
    while(t--)
	{  
        scanf("%d%d",&n,&k);  
        for(int i=0;i<n;i++)  
			for(int j=0;j<n;j++)  
				res[i][j]=(i==j);  
        for(int i=0;i<n;i++)  
			for(int j=0;j<n;j++)  
				scanf("%d",&a[i][j]);  
        pow(a,k);  
        int ans=0;  
        for(int i=0;i<n;i++) 
			ans+=res[i][i];  
        printf("%d
",ans%mod);  
    }  
    return 0;  
}