差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:too_low:ac_automaton [2020/05/31 18:50]
admin fix
+++ 2020-2021:teams:too_low:ac_automaton [2020/06/01 19:30] (当前版本)
admin ↷ 页面technique:ac_automaton被移动至2020-2021:teams:too_low:ac_automaton
@@ 行 1: / 行 1: @@
-====== AC自动机 ======
+**格式**：
+  - 需要注意单词/公式两边与汉字相邻时要有空格（这个我改了一部分）
+  - 如 u，v 之类的结点应当使用数学公式
+  - 题面中存在大量公式书写不规范，已修改，请对照原版检查，以后的 wiki 参照编写
+**内容**：
+  - 部分内容描述不太清晰，我已经修改过了。
+  - 例题 6 中矩阵 E 未定义
+====== AC 自动机 ======
 ===== 一、基础知识 =====
@@ 行 124: / 行 135: @@
 **分析与题解**：求方案数，想到dp，至少包含，可以先求出不符合要求的字符串，最后用总方案数减去不可行的方案数。
-此时题目转化为，有多少长度为M的字符串不包含所有给定的单词，看起来是不是和病毒那题很像？但这题不再是无限长，而且要求求出方案数，考虑一个十分套路的dp
+此时题目转化为，有多少长度为 $M$ 的字符串不包含所有给定的单词，看起来是不是和病毒那题很像？但这题不再是无限长，而且要求求出方案数，考虑一个十分套路的dp：
-$dp[i,j] - > dp[i+1,trie[j].ch[k]]$
+$dp[i,j]\to dp[i+1,trie[j].ch[k]]$
-代表当前长度为$i$时，已经匹配到$j$节点的方案数。主要判断危险节点，要绕开(关于危险节点，见 1.[POI2000]病毒)
+代表当前长度为 $i$ 时，已经匹配到 $j$ 节点的方案数。主要判断危险节点，要绕开（关于危险节点，见 1.[POI2000]病毒）
-再次注意，这个dp方程看似与fail边无关，但是我们在建立fail图的过程中，对于trie树中添加了许多不存在的边，构成了fail图，所以我们在图上跑dp实际上已经在跳fail了，**fail数组只是在匹配后缀，实际上trie图也是由fail数组构造的.**
+再次注意，这个dp方程看似与 fail 边无关，但是我们在建立 fail 图的过程中，对于 trie 树中添加了许多不存在的边，构成了 fail 图，所以我们在图上跑dp实际上已经在跳 fail 了，**fail 数组只是在匹配后缀，实际上 trie 图也是由 fail 数组构造的.**
 这类dp经常与矩阵快速幂结合，见下题。
@@ 行 136: / 行 147: @@
 ==== 5. POJ2778（矩阵快速幂） ====
-**题意**：给定m个长度不超过10 的由ATCG组成的字母串，求出长度为n的不包含这些给定字母串的字符串。**$（m \le 10,n \le 2e9）$**
+**题意**：给定 $m$ 个长度不超过 $10$ 的由 ''ATCG'' 组成的字符串，求出长度为 $n$ 的不包含这些给定字符串的串数量。其中 $m \le 10,n \le 2\times10^{9}$。
 **分析**：是不是看起来和上一题差不多？是不是想用dp？看看数据范围，清醒了吗？正常的dp显然不现实。
-现在我们换一个角度，从**图**的角度来看这个问题，**fail图**.
+现在我们换一个角度，从**图**的角度来看这个问题，**fail 图**。
-我们再来看看上一题写出的状态转移方程，实质上等价于从根节点开始转移，转移$i$次，并且保证不经过危险节点的方案数。再看看数据范围，模式串的长度个数与构成字母都很少，但n却很大，那么我们将fail图去掉危险节点，是不是我们只要求根节点走$n$步到达$j$节点的方案数就可以了？好了，这题的trie图实际上特别小，将trie图用邻接矩阵储存，这题就变成了**矩阵快速幂**；求出$A^n$,最后的答案就是$\sum {A^n[0,i]}$.
+我们再来看看上一题写出的状态转移方程，实质上等价于从根节点开始转移，转移 $i$ 次，并且保证不经过危险节点的方案数。再看看数据范围，模式串的长度个数与构成字母都很少，但 $n$ 却很大，那么我们将 fail 图去掉危险节点，是不是我们只要求根节点走 $n$ 步到达 $j$ 节点的方案数就可以了？好了，这题的 trie 图实际上特别小，将 trie 图用邻接矩阵储存，这题就变成了**矩阵快速幂**；求出 $A^n$，最后的答案就是 $\sum {A^n[0,i]}$。
 ==== 6. HDU2243（矩阵快速幂） ====
-**题意**：给定m个长度不超过5 的字母串，求出长度**不超过**n的至少包含一个这些给定字母串的字符串。**$（m \le 6,n<2^{31}）$**
+**题意**：给定 $m$ 个长度不超过 $5$ 的字符串，求出长度**不超过** $n$ 的至少包含一个给定字符串的串数量。其中 $m \le 6,n<2^{31}$。
-**题解**：$ans=S_n-T_n$
+**题解**：$\text{ans}=S_n-T_n$。
-和上一题很像，但是却要求和，于是我们改造一下矩阵 $$
+和上一题很像，但是却要求和，于是我们改造一下矩阵：
-\begin{bmatrix} A & E \\ 0 & E \end{bmatrix} \times \begin{bmatrix} T_n \\ A \end{bmatrix} = \begin{bmatrix} T_{n+1} \\ A \end{bmatrix}
-$$  A为trie图的邻接矩阵
-==== 7. HDU2825（状压dp） ====
+$$
+\begin{pmatrix} A & E \\ 0 & E \end{pmatrix} \times \begin{pmatrix} T_n \\ A \end{pmatrix} = \begin{pmatrix} T_{n+1} \\ A \end{pmatrix}
+$$
-**题意**:求长度为n，**包含至少k个**模式串的字符串数量。
+其中A为 trie 图的邻接矩阵。
+==== 7. HDU2825（状压dp） ====
-**题解**:好了，现在变成了至少k个，而不是至少一个，我们上面惯用的取反手段失效了。老老实实正面硬刚：子集问题，考虑**状压dp**
+**题意**：求长度为 $n$，**包含至少 $k$ 个**模式串的字符串数量。
-$$dp[i + 1][trie[j][x]][K | num[trie[j][x]]] += dp[i][j][K];$$
+**题解**：好了，现在变成了至少 $k$ 个，而不是至少一个，我们上面惯用的取反手段失效了。老老实实正面硬刚：子集问题，考虑**状压dp**：
+$$dp[i + 1][trie[j][x]][K\lor num[trie[j][x]]] += dp[i][j][K];$$
-$$dp[i][j][k]   $$表示当前走到了字符串的第i位，位于trie的第j个节点上，此时已经匹配的模式串是k（子集状压）
+$dp[i][j][k]$ 表示当前走到了字符串的第 $i$ 位，位于 trie 的第 $j$ 个节点上，此时已经匹配的模式串是 $k$（子集状压）。
 可以看出这个实际上就是之前最简单的那个dp上加了一维信息，维护子集而已。

CVBB ACM Team

用户工具

站点工具

差别

页面工具