文章目录


Tr A HDU1575

题目：

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

题解：

我一开始以为Ak的意思是主对角线各项的k次方的和，发现我太天真了，正确的含义应该是矩阵A的k次幂，然后再求主对角线各项的和
用 矩阵快速幂 来做
也算是模板题把

代码：

#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<list>

using namespace std;

#define maxn 15
int n, k;
struct matrix//定义一个结构体，方便传递值
{
   
    int m[maxn][maxn];
};



matrix mul(matrix a, matrix b)    //矩阵求积, 矩阵乘法
{
   
    matrix ans;
    for(int i = 1; i <= n; i++)
    {
   
        for(int j = 1; j <= n; j++)
        {
   
            ans.m[i][j] = 0;
            for(int k = 1; k <= n; k++)
            {
   
                ans.m[i][j] += (a.m[i][k] * b.m[k][j]) % 9973;
                ans.m[i][j] %= 9973;
            }
        }
    }
    return ans;
}

matrix quick_pow(matrix a, int b)    //矩阵快速幂
{
   
    matrix ans;
    for(int i = 1; i <= n; i++)
    {
   
        for(int j = 1; j <= n; j++)
        {
   
            if(i == j)
                ans.m[i][j] = 1;
            else
                ans.m[i][j] = 0;//这里要初始化为单位矩阵，类比普通快速幂这里初始化为1
        }
    }
    while(b != 0)//方法与普通快速幂相同，只有乘法的实现不同
    {
   
        if(b % 2 == 1)
            ans = mul(a, ans);
        a = mul(a, a);
        b /= 2;
    }

    return ans;
}


int main()
{
   
    int T;
    cin >> T;
    while(T--)
    {
   
        matrix a;

        cin >> n >> k;
        for(int i = 1; i<= n; ++i)
            for(int j = 1; j <= n; ++j)
                cin >> a.m[i][j];

        matrix tmp = quick_pow(a, k);
        int ans = 0;
        for(int i = 1; i<= n; ++i)
            ans += tmp.m[i][i] % 9973;

        ans %= 9973;    // 最后这里一定要再次取余！
        cout << ans << endl;
    }


    return 0;
}