0. Painter’s Studio (POI1998)
- 首先找规律。发现这个分形是每次平分，考虑二进制。
- 容易发现 \(a_{i, j} = 1\) 的条件是不存在任意 \(i\) 使得 \(a_i < b_i\)。
- 考虑平移之后。\((i, j) \rightarrow (i + x, j + y)\) 都要是 \(1\)。问题转化。
- \(f_{i, p, q}\) 表示从低往高第 \(i\) 位，\(p\) 是 \(a + x\) 的进位，\(q\) 是 \(b + y\) 的进位。
1. [bit compressor](Bit Compressor - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
- 确定顺序：从右往左。（存疑）
- 考虑元素：压缩前 \(t_0\) 个 \(0\)，压缩前 \(t_1\) 个 \(1\)。其中 \(t_0 \leq 40\) 比较特殊。
- 转移显而易见。
\(fail_v = [s_v == s_{ch_{fail_u}}]ch_{fail_u}\)
2. [Walk Through Squares](Problem - 4758 (hdu.edu.cn))
- 首先考虑字符串匹配经典做法：字典树，AC 自动机，KMP。
- 把模式串建到 Trie 上，使用 AC 自动机。
- \(f_{i, j, p \in \{0, 1\}, q \in \{0, 1\}, t}\) 表示当前在 \((i, j)\)，是否出现 \(s_1 \or s_2\)，在 Trie 上的节点编号是 \(t\)。
- 转移同 AC 自动机，显然。