hdu 1575 Tr A（矩阵快速幂乘法优化算法）

Problem Description

A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%。

Input

数据的第一行是一个T，表示有T组数据。

每组数据的第一行有n( <= n <= )和k( <= k < ^)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[,]，表示方阵A的内容。

Output

对应每组数据，输出Tr(A^k)%。

Sample Input

Sample Output

Author

xhd

Source

HDU 2007-1 Programming Contest

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define N 10

 #define MOD 9973

 int n,k;

 struct Matrix

 {

     int mp[N][N];

 }matrix;

 Matrix Mul(Matrix a,Matrix b)

 {

     Matrix res;

     int i,j,k;

     for(i=;i<n;i++)

     {

         for(j=;j<n;j++)

         {

             res.mp[i][j] = ;

             for(k=;k<n;k++)

                 res.mp[i][j] = (res.mp[i][j]+(a.mp[i][k]*b.mp[k][j]))%MOD;

         }

     }

     return res;

 }

 Matrix fastm(Matrix a,int b)

 {

     Matrix res;

     memset(res.mp,,sizeof(res.mp));

         for(int i=;i<n;i++)

             res.mp[i][i] = ;

     while(b)

     {

         if(b&)

             res = Mul(res,a);

         a = Mul(a,a);

         b >>= ;

     }

     return res;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&k);

         for(int i=;i<n;i++)

         {

             for(int j=;j<n;j++)

             {

                 scanf("%d",&matrix.mp[i][j]);

             }

         }

         Matrix tmp=fastm(matrix,k);

         int ans=;

         for(int i=;i<n;i++)

         {

             ans=(ans+tmp.mp[i][i])%MOD;

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

hdu 1575 Tr A（矩阵快速幂乘法优化算法）

最新文章

热门文章