网站建设中如何设置外链接,河南省建设厅网站查询,社交网站 建站,网站推广的工作内容文章目录题目#xff1a;题解#xff1a;代码#xff1a;Tr A HDU1575题目#xff1a; A为一个方阵#xff0c;则Tr A表示A的迹#xff08;就是主对角线上各项的和#xff09;#xff0c;现要求Tr(A^k)%9973。 Input 数据的第一行是一个T#xff0c;表示有T组数据。 每…
文章目录题目题解代码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 9Sample Output
2
2686题解
我一开始以为Ak的意思是主对角线各项的k次方的和发现我太天真了正确的含义应该是矩阵A的k次幂然后再求主对角线各项的和 用 矩阵快速幂 来做 也算是模板题把
代码
#includeiostream
#includevector
#includestring
#includecmath
#includealgorithm
#includecstdio
#includecstring
#includelistusing 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;elseans.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;
}
