AcWing 225. 矩阵幂求和（递归）

本文主要是介绍AcWing 225. 矩阵幂求和（递归），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

思路：
用朴素的递归就可以解决。
如果 $k$ 是偶数，那么
$f(A,k)=A^1+A^2+A^3+...+A^k=A^1+A^2+...+A^{\frac{k}{2}}+A^{\frac{k}{2}}(A^1+A^2+A^3...+A^{\frac{k}{2}})$
$= >$
$f(A,k)=f(A,\frac{k}{2})+f(A,\frac{k}{2})*A^{\frac{k}{2}}$

如果 $k$ 是奇数，那么
$f(A,k)=f(A,\frac{k}{2})+A^{\frac{k}{2}+1}+f(A,\frac{k}{2})*A^{\frac{k}{2}+1}$

这就可以直接递归求解了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 207;
const int mod = 2009;
int n,k,m;
int mp[1005];
struct Matrix {int Ma[maxn][maxn];void clear() {memset(Ma,0,sizeof(Ma));}void init() {clear();for(int i = 1;i <= n;i++) {Ma[i][i] = 1;}}
}A,O;
Matrix Mul(Matrix m1,Matrix m2) {Matrix now;now.clear();for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {for(int k = 1;k <= n;k++) {now.Ma[i][j] = (now.Ma[i][j] + m1.Ma[i][k] * m2.Ma[k][j]) % m;}}}return now;
}Matrix Add(Matrix m1,Matrix m2) {Matrix now;now.clear();for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {now.Ma[i][j] = (m1.Ma[i][j] + m2.Ma[i][j]) % m;}}return now;
}
Matrix Qpow(Matrix a,int b) {Matrix now = O;while(b) {if(b & 1) now = Mul(now,a);a = Mul(a, a);b >>= 1;}return now;
}
Matrix dfs(Matrix mat,int k) {if(k == 0) return O;if(k == 1) return mat;Matrix ans;if(k % 2 == 0) {Matrix m1 = dfs(mat,k / 2);ans = Add(m1,Mul(m1, Qpow(mat, k / 2)));} else {Matrix m1 = dfs(mat,k / 2);ans = Add(Qpow(mat,k / 2 + 1),Add(m1,Mul(m1, Qpow(mat, k / 2 + 1))));}return ans;
}
int main() {scanf("%d%d%d",&n,&k,&m);A.clear();for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {scanf("%d",&A.Ma[i][j]);}}O.init();A = dfs(A,k);for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {printf("%d ",A.Ma[i][j]);}printf("\n");}return 0;
}