简介
相对于一般的快速幂，矩阵快速幂仅仅是把他的底数和乘数换成了矩阵形式，而相应的乘法运算什么的也遵循矩阵的运算法则。
矩阵快速幂主要是用于求一个很复杂的递推式的某一项问题,矩阵快速幂的难点主要是在关系矩阵的构造上。
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Matrix {
// 矩阵的行数和列数
int r, c;
int[][] arr;
public Matrix(int r, int c) {
this.r = r;
this.c = c;
this.arr = new long[r][c];
}
// 矩阵乘法
public static Matrix multi(Matrix a, Matrix b) {
// 生成的结果矩阵，行数为 a 的行，列数为 b 的列
Matrix res = new Matrix(a.r, b.c);
for (int i = 0; i < a.r; i++) {
for (int j = 0; j < b.c; j++) {
res.arr[i][j] = res.arr[i][j] + a.arr[i][k] * b.arr[k][j];
}
}
return res;
}
// 矩阵的积（快速幂）
public static Matrix pow(Matrix a, int b) {
Matrix res = a;
b--;
while (b != 0) {
if ((b & 1) == 1) {
res = multi(a, res);
}
a = multi(a, a);
b >>= 1;
}
return res;
}
}
|
例子
单调不下降字符串
我们规定一个（纯小写字母）字符串是单调不下降的，当且仅当它的每个字母，从前往后每个单调不降。比如说 aaaaa 和 aabcd 是单调不下降的，但 aabba 不是。如果给你一个长度为 m 的字符串，问你这样的字符串有多少种，把结果对 20211121 取模。
思路：
- 找到状态方程
- f[i]['a'] = f[i-1]['a'] + f[i-1]['b'] + f[i-1]['c'] + …… + f[i-1]['z']
- f[i]['b'] = f[i-1]['b'] + f[i-1]['c'] + f[i-1]['d'] + …… + f[i-1]['z']
- f[i]['c'] = f[i-1]['c'] + f[i-1]['d'] + f[i-1]['e'] + …… + f[i-1]['z']
- ……
- f[i]['z'] = f[i-1]['z']
- 构造适合此状态方程的矩阵
- 1 1 1 1 …… 1
- 0 1 1 1 …… 1
- 0 0 1 1 …… 1
- ……
- 0 0 0 0 …… 1
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
public class Main {
public static final int MOD = 20211121;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long m = sc.nextLong();
Matrix a = new Matrix(26, 26), f = new Matrix(26, 1);
init(a, f);
a = pow(a, m);
a = multi(a, f);
System.out.println(a.arr[0][0]);
}
// 初始化矩阵
public static void init(Matrix a, Matrix f) {
for (int i = 0; i < 26; i++) {
for (int j = i; j < 26; j++) {
a.arr[i][j] = 1;
}
}
for (int i = 0; i < 26; i++) {
f.arr[i][0] = 1;
}
}
}
class Matrix {
int r, c;
long[][] arr;
public Matrix(int r, int c) {
this.r = r;
this.c = c;
this.arr = new long[r][c];
}
// 矩阵乘法
public static Matrix multi(Matrix a, Matrix b) {
Matrix res = new Matrix(26, 26);
for (int i = 0; i < a.r; i++) {
for (int j = 0; j < b.c; j++) {
for (int k = 0; k < a.c; k++) {
res.arr[i][j] = (res.arr[i][j] + (a.arr[i][k] * b.arr[k][j]) % MOD) % MOD;
}
}
}
return res;
}
// 矩阵乘积
public static Matrix pow(Matrix a, long b) {
Matrix res = a;
b--;
while (b != 0) {
if ((b & 1) != 0) {
res = multi(a, res);
}
a = chengfa(a, a);
b >>= 1;
}
return res;
}
}
|