hdu杭电1575 Tr A

本文主要是介绍hdu杭电1575 Tr A，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

又是一道矩阵快速幂

Tr A

Problem 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

对应每组数据，输出T$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

AC代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 12; //矩阵的行列数 
const int mod = 9973; 
int n, k; //n行n列 
struct mat {int m[maxn][maxn];mat() { //构造函数memset(m,0,sizeof m); for(int i=0;i<=n;++i)m[i][i] = 1;}mat(int x) { //构造函数重载 memset(m,0,sizeof m);}int* operator[](int index) {return m[index];}mat operator*(mat& a){mat res(0);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j) {for(int k=1;k<=n;++k)res[i][j] += m[i][k]*a[k][j];res[i][j] %= mod;}return res;}
}; mat fastPow(mat a,int b)
{mat res;while(b){if(b&1) res = res * a;b >>= 1;a = a*a;}return res;
}int main()
{int t;cin >> t;while(t--){cin >> n >> k;mat a(0);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)cin >> a[i][j];mat res = fastPow(a,k);int sum = 0;for(int i=1;i<=n;++i) sum += res[i][i];cout << sum % mod << endl;}return 0;
}

AC代码2：

#include <bits/stdc++.h>
using namespace std;/**/
const int N = 15;
int n;
int mod;
/**/
struct mat{int m[N][N];mat(){memset(m,0,sizeof(m));for(int i=0;i<n;i++){m[i][i]=1;}}mat operator*(const mat& a){mat res;for(int i=0;i<n;i++){for(int j=0;j<n;j++){res.m[i][j]=0;for(int k=0;k<n;k++){res.m[i][j] += m[i][k] * a.m[k][j];}res.m[i][j] %= mod;}}return res;}
};mat fastpow(mat a,int n){mat res;while(n){if(n&1) res = res*a;n>>=1;a=a*a;}return res;
}int main()
{mod=9973;int T;cin>>T;int nn,kk;while(T--){cin>>nn>>kk;n=nn;mat a;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a.m[i][j];mat res = fastpow(a,kk);int sum=0;for(int i=0;i<n;i++){sum+=res.m[i][i];sum %= mod;}cout<<sum<<endl;}return 0;
}

这篇关于hdu杭电1575 Tr A的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---