HDU - 1575 Tr A(矩阵快速幂)

2019-04-14 11:59发布

站内文章 / 模拟电子
16038 0 1134
Tr A Time Limit: 1000MS
Memory Limit: 32768KB
64bit IO Format: %I64d & %I64u Status 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 题意：A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。
 思路：先求矩阵的 k 次幂，再把对角线元素相加模 m。用快速幂，并且中间就模m，以免溢出。
#include #include #include #include #include #include #include #include using namespace std; const double PI = acos(-1.0); const double e = 2.718281828459; const double eps = 1e-8; int n, k; int m =9973; struct Matrix { int n; int m[10][10]; void clear() { memset(m, 0, sizeof(m)); } }; Matrix multi(Matrix a, Matrix b) { //矩阵乘法 Matrix t; t.clear(); t.n = a.n; for(int i = 0; i < a.n; i++) { for(int j = 0; j < a.n; j++) { for(int k = 0; k < a.n; k++) { t.m[i][j] += a.m[i][k]*b.m[k][j]; } t.m[i][j] %= m; } } return t; } Matrix pow_mod(Matrix a, Matrix b) { //快速幂(反复平发法) while(k) { if(k&1) b = multi(a, b); a = multi(a, a); k >>= 1; } return b; } int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int Case; cin>>Case; while(Case--) { cin>>n>>k; Matrix a, b; a.clear(); b.clear(); a.n = b.n = n; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { scanf("%d", &a.m[i][j]); } }//b为单元矩阵，相当于整数的1 for(int i = 0; i < n; i++) { b.m[i][i] = 1; } b = pow_mod(a, b); int ans = 0; for(int i = 0; i < n; i++) { ans = (ans+b.m[i][i])%m; } cout<





热门文章