Tr A

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

2

2 2

1 0

0 1

3 99999999

1 2 3

4 5 6

7 8 9

 

 

Sample Output

2

2686

 

 

Author

xhd

 

 

Source

HDU 2007-1 Programming Contest

 

 

题解：快速幂+矩阵乘法。注意主对角线是指i=j的那一部分。
#include<cstdio>
#include<iostream>
#define M 9973
using namespace std;
int t,n,k;
long long a[15][15],ans[15][15],sum,d[15][15],b[15][15];
void xx()
{
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++) 
        {
            d[i][j]=0;
            ans[i][j]=0;
        }
    for (int i=1;i<=n;i++)  
      d[i][i]=1; 
    sum=0;
}
void ksm()
{  
    while (k>0)
      {      
          if (k%2) 
            {
                for (int i=1;i<=n;i++)
              for (int j=1;j<=n;j++)
                for (int q=1;q<=n;q++)
                  ans[i][j]=(ans[i][j]+a[i][q]*d[q][j]%M)%M;
            }               
        for (int i=1;i<=n;i++)
          for (int j=1;j<=n;j++)
            {
                b[i][j]=a[i][j];
                a[i][j]=0;
                if (k%2&&k/2) 
                  {
                      d[i][j]=ans[i][j];
                      ans[i][j]=0;
                  }
            }
         for (int i=1;i<=n;i++)
          for (int j=1;j<=n;j++)
            for (int q=1;q<=n;q++)
               a[i][j]=(b[i][q]*b[q][j]%M+a[i][j])%M;
        k/=2;
      }    
}
int main()
{
    scanf("%d",&t);
    while (t--)
      {
           scanf("%d%d",&n,&k);
         xx();
           for (int i=1;i<=n;i++)
             for (int j=1;j<=n;j++)
               scanf("%lld",&a[i][j]);
           ksm();
           for (int i=1;i<=n;i++)
             sum=(sum+ans[i][i])%M;
           cout<<sum<<endl;
      }
    return 0;
}

Recommend

linle