AcWing 3534：矩阵幂 ← 矩阵快速幂

【题目来源】
https://www.acwing.com/problem/content/3537/

【题目描述】
给定一个 n×n 的矩阵 P，求该矩阵的 k 次幂，即 P^k。

【输入格式】
第一行包含两个整数 n 和 k。
接下来有 n 行，每行 n 个整数，其中，第 i 行第 j 个整数表示矩阵中第 i 行第 j 列的矩阵元素 Pij。

【输出格式】
n 行 n 列个整数，每行数之间用空格隔开。

【数据范围】
2≤n≤10,
1≤k≤5,
0≤Pij≤10,
数据保证最后结果不会超过 10^8。

【输入样例】
2 2
9 8
9 3

【输出样例】
153 96
108 81

【算法分析】
● 单变量的快速幂：https://blog.csdn.net/hnjzsyjyj/article/details/143168167
● 矩阵的快速幂与单变量的快速幂的代码非常相似。应用矩阵快速幂的难点在于如何把递推关系转换为矩阵。本题代码，利用了矩阵快速幂实现。可作为矩阵快速幂的模板代码。

【算法代码】

#include<bits/stdc++.h>
using namespace std;const int maxn=10;
const int MOD=1e8+5;struct Matrix {int m[maxn][maxn];Matrix() { //Constructor in structmemset(m,0,sizeof m);}
};/*void add(Matrix &a,Matrix b) { //Matrix additionfor(int i=0; i<maxn; i++)for(int j=0; j<maxn; j++)a.m[i][j]=(a.m[i][j]+b.m[i][j])%MOD;
}*/Matrix mul(Matrix a,Matrix b) { //Matrix multiplicationMatrix ans;for(int i=0; i<maxn; i++)for(int j=0; j<maxn; j++)for(int k=0; k<maxn; k++)ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;return ans;
}Matrix fastPow(Matrix a,int n) {Matrix ans;for(int i=0; i<maxn; i++) ans.m[i][i]=1;while(n) {if(n & 1) ans=mul(ans,a);a=mul(a,a);n>>=1;}return ans;
}int main() {Matrix A;int n,k;cin>>n>>k;for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {cin>>A.m[i][j];}}Matrix t=fastPow(A,k); //Wonderfulfor(int i=0; i<n; i++) {for(int j=0; j<n; j++) {cout<<t.m[i][j]<<" ";}cout<<endl;}return 0;
}/*
in:
2 2
9 8
9 3out:
153 96
108 81
*/

【参考文献】
https://www.acwing.com/solution/content/228922/
https://blog.csdn.net/hnjzsyjyj/article/details/143168167
https://www.cnblogs.com/chenyuhe/p/15837622.html
https://www.luogu.com.cn/problem/solution/P3390