HDU 1575 Tr A——————矩阵快速幂

约定不等于承诺〃 2022-05-09 11:12 164阅读 0赞

# Tr A #

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

#### Problem Description ####

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

##### Input #####

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

##### Output #####

对应每组数据，输出 T r ( A k ) &ThickSpace; % 9973 Tr(A^k)\\;\\%\\ 9973 Tr(Ak)%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

--------------------

简单地矩阵快速幂

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    const int MAXN = 12;
    const int MOD  = 9973;
    ll N;
    struct mat{
        ll m[MAXN][MAXN]; };
    
    mat mul(mat a,mat b)
    {
        
            mat tmp;
            memset(tmp.m,0,sizeof(tmp.m));
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                            for(int k=1;k<=N;k++)
                                    tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
            return tmp;
    }
    mat pow_mod(mat a,ll n)
    {
        
            mat ans;
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                            ans.m[i][j]=(i==j);
            while(n)
            {
        
                    if(n&1) ans=mul(ans,a);
                    a=mul(a,a);
                    n>>=1;
            }
            return ans;
    }
    int main()
    {
        
            ll n,k;
            int t;scanf("%d",&t);
            while(t--)
            {
        
                    scanf("%lld %lld",&n,&k);
                    N=n;
                    mat a;
                    for(int i=1;i<=n;i++)
                            for(int j=1;j<=n;j++)
                                    scanf("%lld",&a.m[i][j]);
                    a=pow_mod(a,k);
                    ll ans=0;
                    for(int i=1;i<=N;i++)
                            ans=(ans+a.m[i][i]+MOD)%MOD;
                    printf("%lld\n",ans);
            }
            return 0;
    }