首页 > 代码库 > 矩阵十题【二】 poj 1575 Tr A 【矩阵】
矩阵十题【二】 poj 1575 Tr A 【矩阵】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1575
题目大意:A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
数据的第一行是一个T,表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
一个矩阵快速幂的裸题。
题解:
#include<iostream> #include<stdio.h> #include<cstring> #define Mod 9973 using namespace std; const int MAX = 11; struct Matrix { int v[MAX][MAX]; }; int n, k, M; Matrix mtMul(Matrix A, Matrix B) // 求矩阵 A * B { int i, j, k; Matrix C; for(i = 0; i < n; i ++) for(j = 0; j < n; j ++) { C.v[i][j] = 0; for(k = 0; k < n; k ++) C.v[i][j] = (A.v[i][k] * B.v[k][j] + C.v[i][j]) % Mod; } return C; } Matrix mtPow(Matrix A, int k) // 求矩阵 A ^ k { if(k == 0) { memset(A.v, 0, sizeof(A.v)); for(int i = 0; i < n; i ++) A.v[i][i] = 1; return A; } if(k == 1) return A; Matrix C = mtPow(A, k / 2); if(k % 2 == 0) return mtMul(C, C); else return mtMul(mtMul(C, C), A); } int solv (Matrix A) { int ans=0; for(int i=0;i<n;i++) ans+=A.v[i][i]%Mod; return ans; } void out(Matrix A) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) printf("%d ",A.v[i][j]); cout<<endl; } } int main () { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); Matrix A; for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&A.v[i][j]); Matrix ans; ans=mtPow(A,k); //out(ans); cout<<solv(ans)%Mod<<endl; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。