任意门：http://acm.hdu.edu.cn/showproblem.php?pid=1575

Tr A

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

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

1 0

0 1

3 99999999

1 2 3

4 5 6

7 8 9

Sample Output

2686

题意概括：如题干

解题思路：矩阵快速幂（本质是二分优化快速进行幂运算）矩阵快速幂模板题

注意：单位矩阵初始化

AC code：

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <cmath>

 #define LL long long

 using namespace std;

 const int MAXN = ;

 const int Mod = ;

 int N;

 struct mat

 {

     int m[MAXN][MAXN];

 }base;

 mat muti(mat a, mat b)

 {

     mat res;

     memset(res.m, , sizeof(res.m));

     for(int i = ; i <= N; i++)

     for(int j = ; j <= N; j++){

             if(a.m[i][j]){

                 for(int k = ; k <= N; k++){

                     res.m[i][k] = (res.m[i][k] + a.m[i][j]*b.m[j][k])%Mod;

                 }

             }

         }

     return res;

 }

 mat qpow(mat a, int n)

 {

     mat res;

     memset(res.m, , sizeof(res.m));

     for(int i = ; i <= N; i++) res.m[i][i] = ;

     while(n){

         if(n&) res = muti(res, a);

         n>>=;

         a = muti(a, a);

     }

     return res;

 }

 int main()

 {

     int K, T_case;

     scanf("%d", &T_case);

     while(T_case--){

         memset(base.m, , sizeof(base.m));

         scanf("%d %d", &N, &K);

         for(int i = ; i <= N; i++){

             for(int j = ; j <= N; j++){

                 scanf("%d", &base.m[i][j]);

             }

         }

         base = qpow(base, K);

         int ans = ;

         for(int i = ; i <= N; i++){

             ans = (ans + base.m[i][i])%Mod;

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

HDU 1575 Tr A 【矩阵经典2 矩阵快速幂入门】

Tr A

题意概括：如题干

解题思路：矩阵快速幂（本质是二分优化快速进行幂运算）矩阵快速幂模板题

最新文章

热门文章