HDU - problem Tr A 【快速幂 + 矩阵】-白红宇

HDU - problem Tr A 【快速幂 + 矩阵】

阅读量：7260 次

发布时间：2019-06-29

本文共 2003 字，大约阅读时间需要 6 分钟。

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4488 Accepted Submission(s): 3377

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 2 1 0 0 1 3 99999999 1 2 3 4 5 6 7 8 9 

Sample Output

      2 2686 

Author

xhd

Source

Recommend

linle | We have carefully selected several similar problems for you:

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 //#include 
                 
                  //#define LOACL#define space " "using namespace std;typedef long long LL;typedef __int64 Int;typedef pair
                  
                    paii;const int INF = 0x3f3f3f3f;const double ESP = 1e-5;const double PI = acos(-1.0);const int MOD = 9973;const int MAXN = 15;int n, m;struct Matrix { LL m[MAXN][MAXN]; int row, col;};Matrix ori, res, u;void init() { memset(res.m, 0, sizeof(res.m)); ori.row = ori.col = n;}void scan_in() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &ori.m[i][j]); } }}Matrix multi(Matrix x, Matrix y) { Matrix z; memset(z.m, 0, sizeof(z.m)); z.row = x.row; z.col = y.col; for (int i = 1; i <= x.row; i++) { for (int k = 1; k <= x.col; k++) { for (int j = 1; j <= y.col; j++) { z.m[i][j] += x.m[i][k]*y.m[k][j]%MOD; } z.m[i][k] %= MOD; } } return z;}Matrix pow_mod(Matrix a, int x){ Matrix b; b.col = a.col; b.row = a.row; memset(b.m, 0, sizeof(b.m)); for (int i = 1; i <= n; i++) { b.m[i][i] = 1; } while(x){ if(x&1) b = multi(a,b); a = multi(a, a); x >>= 1; } return b;}int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); init(); scan_in(); res = pow_mod(ori, m); int ans = 0; for (int i = 1; i <= n; i++) { ans += res.m[i][i]; } printf("%d\n", ans%MOD); } return 0;}