hdu 1575 Tr A （矩阵快速幂模板题）

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年02月21日 星期日 10时28分33秒
  4File Name :code/hdu/1575.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=12;
 34const int MOD = 9973;
 35struct Mat
 36{
 37    int mat[N][N];
 38    void clear()
 39    {
 40	ms(mat,0);
 41    }
 42}A;
 43int n,k;
 44
 45Mat operator * (Mat a,Mat b)
 46{
 47    Mat c;
 48    c.clear();
 49    for ( int i = 0 ; i < n ; i++)
 50	for ( int j = 0 ; j < n ; j++)
 51	    for (int k = 0 ; k < n ; k++)
 52		c.mat[i][j] =(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
 53
 54    return c;
 55
 56}
 57Mat operator ^ (Mat a,int b)
 58{
 59    Mat c;
 60    for ( int i = 0 ; i < n ; i++)
 61	for ( int j = 0 ; j < n ; j++ )
 62	    c.mat[i][j]=(i==j);
 63    while (b)
 64    {
 65	if (b&1) c = c * a;
 66	b = b>>1;
 67	a = a * a;
 68    }
 69    return c;
 70}
 71int main()
 72{
 73	#ifndef  ONLINE_JUDGE 
 74	freopen("code/in.txt","r",stdin);
 75  #endif
 76
 77	int T;
 78	scanf("%d",&T);
 79	while (T--)
 80	{
 81	    scanf("%d %d",&n,&k);
 82	    A.clear();
 83	    for ( int i = 0 ; i < n ; i++)
 84		for ( int j = 0 ; j < n; j ++)
 85		    scanf("%d",&A.mat[i][j]);
 86
 87	    Mat res;
 88	    res.clear();
 89	    res = A^k;
 90
 91	    int ans = 0 ;
 92	    for ( int i = 0 ;  i < n ;i++) ans = (ans +res.mat[i][i])%MOD;
 93
 94	    printf("%d\n",ans);
 95
 96	}
 97
 98
 99  #ifndef ONLINE_JUDGE  
100  fclose(stdin);
101  #endif
102    return 0;
103}