游客 注册 | 登录
中文 | En

1648 - Tr A

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

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

题目输入

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

题目输出

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

输入/输出样例

输入格式

3
1 42
7 
2 6335
0 9 
4 8 
3 29359
2 4 5 
5 1 7 
1 1 5

输出格式

3969
5510
5473

C语言解答

#include<stdio.h>
int main()
{
    int t,n,k,a[11][11],b[11][11],c[11][11],i,j,m,p;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(i=0;i<n;++i)
            for(j=0;j<n;++j)
            {
                scanf("%d",&a[i][j]);
                b[i][j]=0;
                if(i==j)
                    b[i][j]=1;
            }
        for(m=1;m<=k;++m)
            {
                for(i=0;i<n;++i)
                    for(j=0;j<n;++j)
                    {
                        c[i][j]=0;
                        for(p=0;p<n;++p)
                        c[i][j]=c[i][j]+b[i][p]*a[p][j];
                    }
                for(i=0;i<n;++i)
                    for(j=0;j<n;++j)
                        b[i][j]=c[i][j]%9973;
           }
            for(i=j=0;i<n;++i)
                j=j+b[i][i];
            printf("%d\n",j%9973);
    }
    return 0;
}

C++解答

#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 typedef struct Node
 {
     int m[11][11];
 }Matrix;
 Matrix init, unit;  //初始化输入矩阵，单位矩阵如果用递归写Pow函数可以不用单位矩阵
 int n, K;
 void Init( )  //初始化
 {
     scanf( "%d%d", &n, &K );
     for( int i=0; i<n; ++ i )
         for( int j=0; j<n; ++ j )
         {
             scanf( "%d", &init.m[i][j] );
             unit.m[i][j]=( i == j );
         }
 }
 
 Matrix Mul( Matrix a, Matrix b )  //矩阵乘法
 {
     Matrix c;
     for( int i=0; i<n; ++ i )
     {
         for( int j=0; j<n; ++ j )
         {
             c.m[i][j]=0;  //特别注意
             for( int k=0; k<n; ++ k )
             {
                 c.m[i][j] += a.m[i][k]*b.m[k][j];
             }
             c.m[i][j] %= 9973;
         } 
     }
     return c;
 }
 
 Matrix Pow( Matrix a, Matrix b, int k )
 {
     while( k>1 )
     {
         if( k&1 )  // k为奇数时
         {
             k --;
             b=Mul( a, b );
         }
         else   // k为偶数
         {
             k >>= 1;
             a=Mul( a, a );
         }
     }
     a=Mul( a, b );
     return a;
 }
 
 int main( )
 {
     int T;
     scanf( "%d", &T );
     while( T -- )
     {
         Matrix x;
         Init( );
         x=Pow( init, unit, K );
         int sum=0, i=0;
         n--;
         while( n >= 0 )
         {
             sum += x.m[n][n];
             sum%=9973;
             n --;    
         }
         printf( "%d\n", sum%9973 );
     }
 }
请先登陆