2020-2021:teams:too_low:ac_automaton
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:ac_automaton [2020/05/31 18:59] admin update |
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 自动机 ====== | ||
| ===== 一、基础知识 ===== | ===== 一、基础知识 ===== | ||
| 行 136: | 行 147: | ||
| ==== 5. POJ2778（矩阵快速幂） ==== | ==== 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显然不现实。 | **分析**：是不是看起来和上一题差不多？是不是想用dp？看看数据范围，清醒了吗？正常的dp显然不现实。 | ||
| 行 163: | 行 174: | ||
| **题解**：好了，现在变成了至少 $k$ 个，而不是至少一个，我们上面惯用的取反手段失效了。老老实实正面硬刚：子集问题，考虑**状压dp**： | **题解**：好了，现在变成了至少 $k$ 个，而不是至少一个，我们上面惯用的取反手段失效了。老老实实正面硬刚：子集问题，考虑**状压dp**： | ||
| - | |||
| $$dp[i + 1][trie[j][x]][K\lor num[trie[j][x]]] += dp[i][j][K];$$ | $$dp[i + 1][trie[j][x]][K\lor num[trie[j][x]]] += dp[i][j][K];$$ | ||
2020-2021/teams/too_low/ac_automaton.1590922774.txt.gz · 最后更改: 2020/05/31 18:59 由 admin
