2020-2021:teams:intrepidsword:zhongzihao:bm
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:zhongzihao:bm [2020/05/25 11:54] admin 创建 |
2020-2021:teams:intrepidsword:zhongzihao:bm [2020/05/25 12:14] (当前版本) admin |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ===== BM 学习笔记 ===== | + | ====== Berlekamp-Massey 算法 ====== |
| + | |||
| + | ===== 算法介绍 ===== | ||
| 设域 $F$ 上有一无限数列 $s_{0},s_{1},\cdots$，我们想要对某个有限的 $n$，找到一个尽可能短的数列 $c_{1},\cdots,c_{L}$，使得 $s_{j}=-\sum_{i=1}^{L}c_{i}s_{j-i}$ 对 $j=L,L+1,\cdots,n-1$ 成立。特别地，若 $L=0$，意味着 $s_{0}=s_{1}=\cdots=s_{n-1}=0$。记 $s_{0},\cdots,s_{n-1}$ 为 $s^{(n)}$，这样的数列 $c$ 称为 $s^{(n)}$ 的递推式。由定义可以看出，任意 $L\ge n$ 的数列 $c$ 都是 $s^{(n)}$ 的递推式。我们定义长度最小的递推式为最小递推式。下面证明一个重要的引理： | 设域 $F$ 上有一无限数列 $s_{0},s_{1},\cdots$，我们想要对某个有限的 $n$，找到一个尽可能短的数列 $c_{1},\cdots,c_{L}$，使得 $s_{j}=-\sum_{i=1}^{L}c_{i}s_{j-i}$ 对 $j=L,L+1,\cdots,n-1$ 成立。特别地，若 $L=0$，意味着 $s_{0}=s_{1}=\cdots=s_{n-1}=0$。记 $s_{0},\cdots,s_{n-1}$ 为 $s^{(n)}$，这样的数列 $c$ 称为 $s^{(n)}$ 的递推式。由定义可以看出，任意 $L\ge n$ 的数列 $c$ 都是 $s^{(n)}$ 的递推式。我们定义长度最小的递推式为最小递推式。下面证明一个重要的引理： | ||
| 行 71: | 行 73: | ||
| **证明**：假设存在 $i\ge2L$，使得 $c'$ 是 $s^{(i)}$ 的递推式，而不是 $s^{(i+1)}$ 的递推式，那么 $L+L'\ge i+1\ge2L+1$，矛盾。 | **证明**：假设存在 $i\ge2L$，使得 $c'$ 是 $s^{(i)}$ 的递推式，而不是 $s^{(i+1)}$ 的递推式，那么 $L+L'\ge i+1\ge2L+1$，矛盾。 | ||
| + | ===== 例题 ===== | ||
| + | |||
| + | ==== Array Challenge ==== | ||
| + | |||
| + | **题源**：[[http://acm.hdu.edu.cn/showproblem.php?pid=6172|hdu 6172]] | ||
| + | |||
| + | 就是纯 BM。 | ||
| + | |||
| + | ==== The number of circuits ==== | ||
| + | |||
| + | **题源**：2018年牛客多校第 9 场 D | ||
| + | |||
| + | **题目大意**：给定 $k\leq 7$ 和 $n(2k+1\leq n\leq 10^9)$。$n$ 个点的有向图中边为 $i\rightarrow (i+j)\text{ mod } n(\forall j \in [1, k])$，问图中本质不同欧拉路的条数。 | ||
| + | |||
| + | **题解**：best theorem 可知，答案为： | ||
| + | |||
| + | $$ | ||
| + | t_w(G)\prod_{i=1}^n(\deg(i) - 1)!=t_w(G)\cdot ((k-1)!)^n | ||
| + | $$ | ||
| + | |||
| + | 考虑计算 $t_w(G)$，用 matrix-tree 定理，可以发现对于固定的 $k$，$n$ 是满足线性递推关系的，我们用 BM 计算即可。 | ||
| + | |||
| + | ==== Expected Value ==== | ||
| + | |||
| + | **题源**：Petrozavodsk Winter-2019. 300iq Contest 1 E | ||
| + | |||
| + | **题目大意**：给你一个连通平面图，开始在 $1$。每次等概率随机走到一个邻点，问第一次走到 $n$ 的期望次数。 | ||
| + | |||
| + | **题解**：由于可以用矩阵递推，考虑用 BM 求解。由于平面图满足 $E\le3V-6(V\ge3)$，因此这部分的复杂度为 $\mathcal{O}(V^{2})$。 | ||
| + | |||
| + | 假设 $P(x)=\sum_{i=0}^{+\infty}p_{i}x^{i}$，$Q(x)$ 为递推式，设 $R(x)=P(x)Q(x)$，显然 $R(x)$ 只有前 $V$ 项不为 $0$。我们所求即为 $$ | ||
| + | \begin{aligned} | ||
| + | &P'(1)\\ | ||
| + | =&(\frac{R}{Q})'(1)\\ | ||
| + | =&\frac{R'(1)Q(1)-R(1)Q'(1)}{Q^{2}(1)} | ||
| + | \end{aligned} | ||
| + | $$ 这部分的时间复杂度也为 $\mathcal{O}(V^{2})$，用 FFT 可以加速到 $\mathcal{O}(V\log V)$。 | ||
| + | |||
| + | 时间复杂度 $\mathcal{O}(V^{2})$。 | ||
| + | |||
| + | ==== Fresh Matrix ==== | ||
| + | |||
| + | **题源**：Petrozavodsk Winter-2018. ITMO U 1 Contest F | ||
| + | |||
| + | **题目大意**：定义一个 $01$ 矩阵是好的，当且仅当所有 $1$ 都不相邻，所有 $0$ 相互四连通。问有多少种 $n\times m$ 的好的 $01$ 矩阵，对质数取模。$n\le11,m\le10^{9}$。 | ||
| + | |||
| + | **题解**：对列记录该列有哪些格子是 $1$，以及 $0$ 的格子之间的连通情况，状态有 $2161$ 个，转移有 $96219$ 个。然后 ''%%BM%%'' 即可。 | ||
| + | |||
| + | 复杂度 $\mathcal{O}(ST+S^{2}\log m)$。如果你想用 ''%%FFT%%'' 优化到 $\mathcal{O}(ST+S\log S\log m)$，那自然也是极好的。不过抄板可能会累死你 : P | ||
| + | |||
| + | ===== 参考文献 ===== | ||
| + | |||
| + | [1] Massey J. Shift-register synthesis and BCH decoding[J]. IEEE transactions on Information Theory, 1969, 15(1): 122-127. | ||
2020-2021/teams/intrepidsword/zhongzihao/bm.1590378887.txt.gz · 最后更改: 2020/05/25 11:54 由 admin
