关于数论:数论矩阵快速幂-CH-Tr-A复试上机试题

A 为一个方阵，则 Tr A 示意 A 的迹（就是主对角线上各项的和），现要求 Tr(A^k)%9973。

输出
数据的第一行是一个 T，示意有 T 组数据。每组数据的第一行有 n(2 <= n <= 10)和 k(2 <= k < 10^9)两个数据。接下来有 n 行，每行有 n 个数据，每个数据的范畴是[0,9]，示意方阵 A 的内容。

输入
对应每组数据，输入 Tr(A^k)%9973。

样例输出 Copy
3
1 42
7
2 6335
0 9
4 8
3 29359
2 4 5
5 1 7
1 1 5
样例输入 Copy
3969
5510
5473

参考 https://www.cnblogs.com/cmmdc…

//#include<iostream>
//#include<algorithm>
//#include<cstring>
//#include<string.h>
//#include<cmath>
//#include <cstdlib>
//using namespace std;
///*
// 
//*/
//typedef struct Node{//    int m[11][11];
//}Matrix;// 创立一个矩阵构造体 
//Matrix init;// 定义一个构造体变量来存输出的数据
//Matrix unit; 
//int n,k;// n 方阵的行列数，k 为要求的方阵的迹的幂值(^k), 均为全局变量 
//void Init(){// 没有参数的函数  1, 返回值类型 函数名（void）2, 返回值类型 函数名（）//    scanf("%d %d",&n,&k);
//    for(int i = 0; i < n; i++){//        for(int j = 0; j < n; j++){//            scanf("%d",&init.m[i][j]);
//            unit.m[i][j] = (i == j);
//        }
//    }
//}
//Matrix Mul(Matrix a, Matrix b){
//    Matrix c;
//    for(int i = 0; i < n; ++i){//        for( int j = 0; j < n; ++j){//            c.m[i][j] = 0;// 置长期矩阵初值为空（0）//            for(int k = 0; k < n; ++k){//                c.m[i][j] += a.m[i][k]*b.m[k][j];// 计算新矩阵的每一个想乘的值 
//            } 
//            c.m[i][j] %= 9973;
//        }
//    }
//    return c;
//} 
//Matrix Pow(Matrix a,Matrix b,int k){// 矩阵疾速幂，k 为幂指数
////Matrix Pow(Matrix a,int k){// 矩阵疾速幂，k 为幂指数
////    Matrix b;// 定义一个作为单位矩阵
////    memset(b.m,0,sizeof(b.m));// 初始化输出矩阵 void *memset(void *s,  int c, size_t n); 
////    //memset: 作用是在一段内存块中填充某个给定的值，它对较大的构造体或数组进行清零操作的一种最快办法
////    for(int i = 0; i < n; i++){////        for(int j = 0; j < n; j++){////            if(i == j){////                b.m[i][j] = 1;// 单位矩阵对角线值为 1
////            }else{////                b.m[i][j] = 0;
////            }
////        }
////    } 
//    while(k){// 矩阵疾速幂 
//        if(k&1){// 位运算 k 的二进制与 1 的二进制（00000001）相与，都为 1 才为 ture, 其实就是判断为奇数 乘上矩阵 a 
//            b = Mul(b,a);// 此处疾速幂模板，参考第一行 blog 
//        }// k 的二进制最初一位是 0, 即为偶数 将矩阵 a 平方
//        a = Mul(a,a);
//        k >>= 1;// 位运算，k 的二进制右移一位，相当于 k = k >> 1; 如 8 二进制数为 00001000, 进行 >>1 右移一位后就是 00000100
//    } 
//    return b;
//}
//int main(){
//    int t = 0;
//    scanf("%d",&t);
//    while(t--){
//        Matrix x;// 定义一个矩阵来接管疾速幂（Pow 函数）的返回值矩阵
//        Init(); 
////        x = Pow(init,k);
//        x = Pow(init,unit,k);
//        int sum = 0;// 计算迹的幂的和 
//        for(int i = 0; i < n; i++){//            sum += x.m[i][i];
//            sum %= 9973;
//        } 
//        printf("%d\n",sum);
//    }
//    return 0;
//}