?
Tr A
| Time Limit: 1000MS |
? |
Memory Limit: 32768KB |
? |
64bit IO Format: %I64d & %I64u |
?
SubmitStatus
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<
?