题解：P10502 Matrix Power Series
vicissitudes
·
·
题解
Matrix Power Series 矩阵幂求和
写不来分治，只好慢慢推公式。
引理：两个矩阵相乘能分解为若干个矩阵相乘（如果能的话）。
即：
\begin{matrix}
A B
\end{matrix}
\right]\times
\left[
\begin{matrix}
CD\\
EF
\end{matrix}
\right]=
\left[
\begin{matrix}
A\times C + B\times E & A\times D+B\times F
\end{matrix}
\right]
$$，
其中 $ABCDEF$ 均为大小相等的**矩阵**。
~~可以手算。~~
## 本题思路
令 $F_n = [A_n,S_n]$ ，其中 $A_n$ 与 $S_n$ 均为题目含义。
$B$ 为 $2n\times2n$ 的矩阵。
列得：
$$[A_n,S_n]\times B=[A_{n + 1}, S_{n + 1}]$$，
已知：
$$A_{n+1} = A_n \times A$$，
$$S_{n+1} = S_n + A_{n+1}$$，
推导可得：
$$B =\left[
\begin{matrix}
A&A\\
0&E
\end{matrix}
\right]
$$。
其中 $A$ 为题目所给，
$E$ 为单位矩阵。
即：
$$F_{n} = F_1\times B^{k-1}$$。
**快速幂**计算即可。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 80;
long long n, k, m;
long long a[N][N], b[N][N];
void mul1(long long c[][N], long long a[][N], long long b[][N]) {
long long temp[N][N] = {0};
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= 2 * n; j ++) {
for(int k = 1; k <= 2 * n; k ++) {
temp[i][k] = (temp[i][k] + a[i][j] * b[j][k] % m) % m;
}
}
}
memcpy(c, temp, sizeof temp);
}//n * 2n的矩阵与2n * 2n的矩阵相乘
void mul2(long long c[][N], long long a[][N], long long b[][N]) {
long long temp[N][N] = {0};
for(int i = 1; i <= 2 * n; i ++) {
for(int j = 1; j <= 2 * n; j ++) {
for(int k = 1; k <= 2 * n; k ++) {
temp[i][k] = (temp[i][k] + a[i][j] * b[j][k] % m) % m;
}
}
}
memcpy(c, temp, sizeof temp);
}//2n * 2n的矩阵与2n * 2n的矩阵相乘
int main() {
cin >> n >> k >> m;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n; j ++) {
cin >> a[i][j];
a[i][j + n] = a[i][j];//F1 = [A A]
b[i][j] = b[i][j + n] = a[i][j];
b[i + n][i + n] = 1;//B = [A A
} //0 E]
}
k --;
while(k) {
if (k & 1) mul1(a, a, b);
k /= 2;
mul2(b, b, b);
}//矩阵快速幂
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n; j ++) {
cout << (a[i][j + n] + m) % m << " ";//输出Fn的Sn
}
puts("");
}
return 0;
}
```