首页 > 代码库 > hdu 1575

hdu 1575

2024-08-08 04:36:40   215人阅读

Tr A

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3032    Accepted Submission(s): 2263


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
22 21 00 13 999999991 2 34 5 67 8 9
 

 

Sample Output
22686
 

 

Author
xhd
 

 

Source
HDU 2007-1 Programming Contest
 

 

Recommend
 
矩阵乘法+快速幂
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<cstdlib>#include<queue>#include<set>#include<vector>using namespace std;#define M 9973int T,n,k;struct matri{      int f[10][10];};matri mul(matri a,matri b){     matri c;     memset(c.f,0,sizeof(c.f));     for(int k=0;k<n;k++)            for(int i=0;i<n;i++)            {                if(!a.f[i][k]) continue;                for(int j=0;j<n;j++)                {                   if(!b.f[k][j]) continue;                   c.f[i][j]=(c.f[i][j]+a.f[i][k]*b.f[k][j])%M;                }            }      return c;}matri pow_(matri a,int b){     matri s;     memset(s.f,0,sizeof(s.f));     for(int i=0;i<n;i++)            s.f[i][i]=1;     while(b)     {         if(b&1)            s=mul(s,a);         a=mul(a,a);         b=b>>1;     }     return s;}int main(){     scanf("%d",&T);     while(T--)     {        matri e;        scanf("%d%d",&n,&k);        for(int i=0;i<n;i++)            for(int j=0;j<n;j++)                  scanf("%d",&e.f[i][j]);        e=pow_(e,k);        int ans=0;        for(int i=0;i<n;i++)            ans=(ans+e.f[i][i])%M;        printf("%d\n",ans);     }     return 0;}

　　

hdu 1575


联系
我们