2019.8.11 集训笔记

今天机房里一些人被刷了一下 D 盘,还好我昨天备份了一下 qwq

但是恢复备份用了我几十分钟,这电脑是真的 傻逼….


上午讲 $KMP$ 、$Tire$ 、$AC$ 自动机,过去听了个 $AC$ 自动机就溜了,什么马拉车对我来说都不重要 qwq

讲座中又提到了矩阵乘法,老师甚至觉得矩阵乘法比 $AC$ 自动机更基础 QAQ,我太菜了…..

笔记

矩阵乘法

众所周知,做矩阵乘法有一些规定,若矩阵 $C = A \times B$,则:

  • $A$ 的列数必须和 $B$ 的行数相等
  • 若 $A$ 为 $n \times p$ 的矩阵,$B$ 为 $p \times m$ 的矩阵,那么 $C$ 为 $n \times m$ 的矩阵
  • 对于 $C$ 中每一个数,$C_{i,j} = \sum\limits_{k=1}^{p} a_{i,j} \times b_{i,j}$ 。通俗一点来说就是 $C$ 中的第 $i$ 行第 $j$ 列的值为 $A$ 中第 $i$ 行中每一个对应的值与 $B$ 中第 $j$ 列每一个对应的值之积的和。

有一个一本通上的例子:

反正差不多就酱紫,对应的行和列上每一个数的乘积之和就是答案 qwq

例题

$Fibonacci$ 第 $n$ 项的值

这是一本通上的例题 qwq

这题朴素算法最快到 $O(n)$ ,但是如果当 $1 \leq n \leq 2 \times 10 ^9$ 的时候,就连 $O(n)$ 都跑不过了。我太菜了,暂时不会推出矩阵乘法,所以就先记下过程找找感觉:

因为,

所以,递推式可以转化为矩阵乘法:

这个时候矩阵快速幂就出来了,所以时间复杂度为 $O( \log n) $ 。

代码有时间在写….

$Code$:

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
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 2;
const int Mod = 1e9 + 7;

struct Node {
long long g[MAXN + 5][MAXN + 5];
};
Node f, temp;

long long n, ans;

inline void MatrixInit (Node &x) {
for (int i = 1; i <= MAXN; i++) {
for (int j = 1; j <= MAXN; j++) {
if (i == j) x.g[i][j] = 1LL;
else x.g[i][j] = 0LL;
}
}
return;
}

inline void MatrixX (Node &x, Node &y, Node &z) {
memset (z.g, 0, sizeof (z.g));

for (int i = 1; i <= MAXN; i++) {
for (int j = 1; j <= MAXN; j++) {
if (!x.g[i][j]) continue;
for (int k = 1; k <= MAXN; k++) {
z.g[i][k] += x.g[i][j] * y.g[j][k];
z.g[i][k] %= Mod;
}
}
}
return;
}

inline void Pow (long long m) {
MatrixInit (temp);
Node res = f, t;
while (m >= 1) {
if (m & 1) {
MatrixX (temp, res, t);
temp = t;
}
MatrixX (res, res, t);
res = t;
m >>= 1;
}
return;
}

long long solve () {
if (n <= 2) return 1;
Pow (n - 2);
long long ans = temp.g[1][1] * 1 + temp.g[2][1] * 1;
ans %= Mod;
return ans;
}

int main() {
scanf ("%lld", &n);
f.g[1][1] = 1;
f.g[1][2] = 1;
f.g[2][1] = 1;
f.g[2][2] = 0;
printf ("%lld\n", solve());
return 0;
}

$Fibonacci$ 求前 $n$ 项和

设 $s[i]$ 表示前 $i$ 项和,

因为,

所以,

然后再套入通项公式即可。

代码依然懒得打….

总结

希望矩阵乘法不会考的太难,一般转化的做法就是把需要求的东西,往式子里面套,前面的系数一般都为 0 或 1 。然后就出来了??(雾)

$AC$ 自动机

这个知识点也是在很久很久以前就咕咕咕了 qwq

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×