【模板】【数学】矩阵快速幂

 1 int n; // 所有矩阵都是 n * n 的矩阵
 2 struct matrix {
 3    int a[100][100];
 4 };
 5 matrix matrix_mul(matrix A, matrix B, int mod) {
 6     // 2 个矩阵相乘
 7     matrix C;
 8     for (int i = 0; i < n; ++i) {
 9         for (int j = 0; j < n; ++j) {
10             C.a[i][j] = 0;
11             for (int k = 0; k < n; ++k) {
12                 C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
13             }
14         }
15     }
16     return C;
17 }
18 matrix unit() {
19     // 返回一个单位矩阵
20     matrix res;
21     for (int i = 0; i < n; ++i) {
22         for (int j = 0; j < n; ++j) {
23             if (i == j) {
24                 res.a[i][j] = 1;
25             } else {
26                 res.a[i][j] = 0;
27             }
28         }
29     }
30     return res;
31 }
32 matrix matrix_pow(matrix A, int n, int mod) {
33     // 快速求矩阵 A 的 n 次方
34     matrix res = unit(), temp = A;
35     for (; n; n /= 2) {
36         if (n & 1) {
37             res = matrix_mul(res, temp, mod);
38         }
39         temp = matrix_mul(temp, temp, mod);
40     }
41     return res;
42 }