题意
给定一个n*n大小的矩阵A，求以A为公比的等比数列的前k项和。
解题思路
直接从1到k矩阵快速幂每项相加肯定是会超时的，而如果用公式计算需要求逆矩阵非常麻烦，而且有可能会溢出。
因此我们使用分治求解。
当n为奇数时，
当n为偶数时，
分治求解即可。
#include <bits/stdc++.h> using namespace std; struct matrix { int a[31][31]; }; int n, k, m; matrix st, base; matrix add(matrix a, matrix b) { matrix res; for (int i = 1; i <= n;i++) for (int j = 1; j <= n;j++) res.a[i][j] = (a.a[i][j] + b.a[i][j]) % m; return res; } matrix multi(matrix a, matrix b) { matrix res; memset(res.a, 0, sizeof(res.a)); for (int i = 1;i<=n;i++) for (int j = 1; j <= n;j++) for (int p = 1; p <= n;p++) res.a[i][j] = (res.a[i][j] + a.a[i][p] * b.a[p][j]) % m; return res; } matrix fastpow(int p) { matrix a = st; matrix b = base; while(p) { if(p&1) b = multi(b, a); a = multi(a, a); p = p >> 1; } return b; } matrix dfs(int p) { if(p==1) return st; matrix ans, temp; ans = dfs(p / 2); temp = fastpow(p / 2); ans = add(ans, multi(ans, temp)); if(p&1) ans = add(ans, fastpow(p)); return ans; } signed main() { std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> m; for (int i = 1; i <= n;i++) for (int j = 1; j <= n;j++) { cin >> st.a[i][j]; if(i==j) base.a[i][j] = 1; else base.a[i][j] = 0; } matrix res; res = dfs(k); for (int i = 1;i<=n;i++) { for (int j = 1; j <= n;j++) { if(j!=1) cout<<" "; cout << res.a[i][j]; } cout << endl; } return 0; }