HDU 1575 矩阵快速幂 模板题

本文主要是介绍HDU 1575 矩阵快速幂 模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Tr A

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8149    Accepted Submission(s): 5923

 

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

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

 

 

Author

xhd

 

 

Source

HDU 2007-1 Programming Contest

 

 

Recommend

linle   |   We have carefully selected several similar problems for you:  1757 1588 2256 2604 2254 

 

矩阵快速幂的模板提，矩阵快速幂的本质和普通快速幂一样一样的

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define N 10005  
using namespace std;
const int p= 9973;
const int MAXN= 100;
typedef long long ll;
int n,m;
struct Matrix
{long long M[MAXN][MAXN];Matrix(const bool I = 0)  ///初始化对角矩阵{memset(M, 0, sizeof(M));if (I)for(int i = 0; i < n; i++) M[i][i] = 1;}Matrix operator *(const Matrix &y) ///矩阵乘法，对乘法重新定义{Matrix z;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)for (int k = 0; k < n; k++)z.M[i][j] = (z.M[i][j]+M[i][k]*y.M[k][j]%p)%p;return z;}void out(){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++)cout << M[i][j] << " ";cout << "\n";}}
};
Matrix pow(Matrix A, long long b)///矩阵的快速幂{Matrix ans = Matrix(1);for (; b; b>>=1){if (b&1) ans = ans*A;A = A*A;}return ans; }
int a[100][100];
int main()  
{  int T;cin>>T;while(T--){Matrix temp;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>temp.M[i][j];}}temp=pow(temp,m);ll ans=0;for(int i=0;i<n;i++){ans=(ans+temp.M[i][i])%p;}printf("%lld\n",ans);}return 0;  
}  

 

这篇关于HDU 1575 矩阵快速幂 模板题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---