自动搬运

查看原文

来自洛谷，原作者为

	vicissitudes 雨一直下

搬运于2025-08-24 22:58:38，当前版本为作者最后更新于2024-06-10 21:22:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Matrix Power Series 矩阵幂求和

写不来分治，只好慢慢推公式。

引理：两个矩阵相乘能分解为若干个矩阵相乘（如果能的话）。

即：

$$\left[ \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 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; } ```$$