对所有串建出 AC 自动机，如果能够找到一个不经过终止状态的环，则存在一条无限长的不包含所有模式串的 01 串。
对所有串建出 AC 自动机，如果能够找到一个不经过终止状态的环，则存在一条无限长的不包含所有模式串的 01 串。
给定多个字符串，多次询问 $x$ 串在 $y$ 串中出现了多少次。
$x$ 在 $y$ 中的每次出现都恰对应 AC 自动机上的一个节点，使得这个节点为 $y$ 的前缀（在 Trie 树上为 $y$ 的祖先），并且这个节点存在后缀 $x$（在失配树上为 $x$ 的后代），这个点即结尾于该次出现的右端点的前缀。
也即我们需要查询 Trie 树上从根到 $y$ 这一条路径上，有多少在失配树上以 $x$ 为根的子树内。于是用树状数组根据 dfs 序维护子树和，在 Trie 树上 dfs，动态维护当前所在的点到根这一条路径上所有点，在树状数组上做单点加减，区间求和。
核心在于维护失配指针，即每个节点指向 Trie 中存在的最长真后缀。
先建出 Trie 树。将根节点的后继节点加入作为起始节点 bfs。
bfs 的过程中，对于当前节点遍历字符集中的每个字符 $c$。
不难发现从一个节点走向它失配指针指向的位置，它所代表的字符串的长度单调减少。因此从一个节点一直这样走，最后一定能够走到 Trie 的根节点。于是失配指针的关系构成了有根一棵树，以每个节点为根的子树即以这个节点为后缀的所有节点。
对于某个字符串 $w=a_1,\cdots,a_n\in\Sigma^\ast(a_1,\cdots,a_n\in\Sigma)$ 和 $t\in\Sigma^\ast$，$\operatorname{end-pos}_w(t)=\{i\mid t=a_{i-|y|+1}\cdots a_i\}$。特殊地，$\operatorname{end-pos}_w(\lambda)=\{0,1,2,\cdots,n\}$。不会混淆的情况下可以简记作 $\operatorname{end-pos}(t)$。
称字符串 $s$ 的两个子串 $x,y$ 右端点等价，当且仅当 $\operatorname{end-pos}_w(x)=\operatorname{end-pos}_w(y)$，记作 $x\overset w\equiv y$，简记作 $x\equiv y$。右端点等价显然是一种等价关系，于是我们可以将 $x$ 所在的等价类记作 $[x]_w$，简记作 $[x]$。
引理 1.1 显然：
如果 $x$ 为某个等价类中最长的子串，我们称 $x$ 代表该等价类。
DAWG（Directed Acyclic Word Graph）$D_w$ 定义为满足以下条件的有限状态自动机：
下文混用“状态”与“右端点等价类”两种说法。
引理 1.2 $D_w$ 能够识别 $w$ 的所有子串。
证明： 构成 $D_w$ 的接受状态的右端点等价类的并即该字符串的所有子串，由 Nerode 定理易证。$\Box$
DAWG 不一定是能够识别 $w$ 的所有子串的最小 DFA。
SAM（Suffix Automaton）$S_w$ 定义为，在 $D_w$ 的基础上，将接受状态改为所有后缀所在的等价类，即 $\operatorname{end-pos}$ 值包括 $|w|$ 的所有等价类。
定理 1.3 对于任意 $w\in S^\ast$，$S_w$ 是最小的能够识别 $w$ 所有后缀的有限状态自动机
证明： 由定义，$S_w$ 所有接受状态的并集即 $w$ 的所有后缀，所以 $S_w$ 能够识别 $w$ 的所有后缀。欲证明最小性，不难发现对于任意 $x\equiv y$ 和 $z\in\Sigma^\ast$，$xz$ 是 $w$ 后缀当且仅当 $yz$ 是 $w$ 后缀，于是由 Nerode 定理易证。$\Box$
如果两个子串的 $\operatorname{end-pos}$ 集合有交，那么其中一个一定是另一个的子串，于是前者的 $\operatorname{end-pos}$ 值是后者的 $\operatorname{end-pos}$ 值的超集。所以某个字符串 $w$ 的所有等价类能够由此关系构造一棵有根树，使得 $\operatorname{end-pos}(u)$ 是 $\operatorname{end-pos}(v)$ 的超集当且仅当 $u$ 在树上为 $v$ 的祖先。下文把这棵树称作 parent 树 $T(w)$。
定理 1.4 如果 $x$ 在 $w$ 中代表某个等价类 $[x]$，那么 parent 树上该等价类的子节点为 $[ax]$，其中 $a\in\Sigma$，且 $ax$ 在 $w$ 中至少出现过一次。
证明 根据定义，$[x]$ 在 $T(w)$ 上子节点对应的 $\operatorname{end-pos}$ 为所有极大的合法的 $\operatorname{end-pos}(x)$ 的真子集，即一定能够表示为某个 $\operatorname{end-pos}(ax)$，其中 $a\in\Sigma$。$\Box$
由定理 1.4，$T(w)$ 为 $w$ 反串的后缀树。
引理 1.5 对于长度大于等于 $2$ 字符串 $w$，$S_w$ 最多有 $2|w|-1$ 个状态。
证明 特别地，对于 $w=a^n$（$n>2$），$S_w$ 有 $n+1$ 个状态。否则我们将 $T(w)$ 上的所有节点分类讨论。
如果某个子串 $x$ 在 $w$ 中两个位置出现时左侧紧邻不同字符，那么 $[x]$ 至少有两个子节点。因此根据引理 1.1 的 4，只有 $0$ 个或 $1$ 个子节点的等价类的代表元一定是 $w$ 的前缀。因为某个前缀只能出现在一个等价类中，并且由于 $w$ 由至少两种字符构成，$[\lambda]$ 至少有 $2$ 个子节点，所以有 $0$ 个或 $1$ 个子节点的等价类不多于非空前缀，所以最多有 $|w|$ 个。
而因为树的性质，至少有 $2$ 个子节点的节点个数少于总节点数的一半，所以总节点数少于有 $0$ 个或 $1$ 个子节点的节点个数的两倍，即最多有 $2|w|-1$ 个。$\Box$
$S_w$ 节点数达到此上界，当且仅当 $w=ab^n$，其中 $a\not=b$，在此不做证明。
引理 1.6 对于长度大于等于 $2$ 的字符串 $w$，$S_w$ 的转移边数最多比状态数多 $|w|-2$。
证明 对于 $S_w$ 的任一生成树，其树边比状态数少 $1$。而对于每一条非树边 $(p,q)$，都可以构造出至少一条从 $[\lambda]$ 到 $[w]$ 的路径，使得该非树边为路径中第一条非树边。具体构造方案为：在生成树上从 $[\lambda]$ 到 $p$，从 $p$ 到 $q$，因为 $S_w$ 上仅有 $[w]$ 一个点出度为零并且图上无环，所以至少存在一条从 $q$ 到 $[w]$ 的路径。因为 $w$ 有 $|w|-1$ 个后缀经过了至少一条非树边，每个后缀对应唯一一条从 $[\lambda]$ 到 $[w]$ 的路径，所以非树边最多有 $|w|-1$ 条。于是有 $S_w$ 的转移边数最多比状态数多 $|w|-2$。$\Box$
结合引理 1.5 和引理 1.6 有如下结论。
定理 1.7 对于长度大于 $2$ 的字符串 $w$，$S_w$ 的状态数最多为 $2|w|-1$，转移边数最多为 $3|w|-4$。
证明 由引理 1.6，转移边数不超过状态数加 $|w|-2$。因此转移边数一个较松的上界为 $3|w|-3$。转移边数达到这个上界，仅当状态数达到 $2|w|-1$ 的上界，即 $w$ 形如 $ab^n$，此时转移边数为 $2|w|-1$，无法达到该上界。因此转移边数的上界为 $3|w|-4$。
达到该上界当且仅当 $w=ab^nc$，其中 $a,b,c$ 两两不同。
考虑对从短到长每个前缀依此建出其对应的 SAM。于是只需要考虑一个字符串末尾加入某个字符后 SAM 的变化即可。
对每条线 DP，从上往下安排折线形态。
因为前一条线对当前的线有限制，所以需要计入状态。即状态应与已分配过的线数 $n$、当前线已安排的行数 $i$、左侧第一条线的形态 $T$，当前线已安排的形态 $S$ 有关。
发现状态中存在一些冗余信息：
我们不关心上一条折线 $T$ 第 $i$ 行以上的走势，只关心当前线 $S$ 到 $T$ 在第 $i$ 行上之间的宽度。
再次深入考虑后我们发现 $T$ 的第 $i$ 行一下的某一部分我们也不关心。
如果，我们安排当前线以下部分一直向左直到撞到上一条线，至少一直向左的部分长为 $k$，那么折线 $T$ 的第 $i$ 行一下的 $k$ 段，其形态我们也不关心。
又想到 $S$ 的长度仅为 $i$，$T$ 中我们只关心 $i$ 以下一直向左走多久会被撞到，和撞到的位置以下 $T$ 的形态，我们可以巧妙地设置状态。
这个状态的意义为，第 $i$ 行及以上部分为当前安排的折线形态 $S$，以下为尽量往左走，能够走出的形态。
这样将复杂度优化到 $O(n^22^n)$。
[CF1842D] Tenzing and His Animal Friends
首先以 $m$ 条 special restrictions 为边建一幅无向图，对于某一分钟的选取方案，我们定义关键边为两侧的点一个被选中，另一个未被选中的边。
然后考察任意一条 $1\to n$ 的路径，不难发现，点 $1$ 总需要被选取，点 $n$ 不可以被选取，因此任何一种选取朋友的方案的任意一刻，这条路径上至少有一条关键边。而在一种游戏方案中，每一条边为关键边的时间不超过它的边权。于是游戏时长不可能超过 $1\to n$ 的任意一条路径的长度，也就不可能超过 $1\to n$ 的最短路。
证明了游戏时长存在一个上界，现在需要构造一种方案使得游戏时长能够达到这个上界。记 $d_i$ 为 $1\to i$ 的最短路，点 $i$ 在 $[1,d_i)$ 这个时间段不被选取，在 $[d_i,d_n]$ 的时间段被选取，于是任意一条边权为 $w$ 的边 $(u,v)$ 满足 $|d_u-d_v|\le w$（最短路的性质），而前者即这条边作为关键边的时长，从而保证了题目的 special restrictions 成立。
然后就可以如此构造答案。
分块并维护块内排序后的结果，设块长为 $B$。
区间加时，整块打 tag，散块暴力修改后排序。
区间查询 rank，整块二分，散块暴力统计。
这样时间复杂度为 $O(q\log(B)(\dfrac nB+B))$
考虑到区间加时，散块中被修改的和未被修改的部分内部，相对大小关系不变，可以 $O(B)$ 归并。
这样时间复杂度为为 $O(q\log(B)\dfrac nB+qB)$，$B$ 取 $\sqrt{n\log n}$ 以平衡复杂度。
类似地，分块维护块内排序内的结果，设块长为 $B$。
区间加时，整块打 tag，散块同样 $O(B)$ 归并。
区间查询第 k，通过二分答案转化为查询 rank。
这样时间复杂度为 $O(q\log(w)(\dfrac nB+B))$。
二分后，在散块中查询 rank 时可以将至多两个散块归并到一个新数组，从而将查询 rank 的 $O(B)$ 的时间复杂度变为 $O(\log B)$。
这样时间复杂度为 $O(q\log(w)(\dfrac nB\log B+\log B)+q(\dfrac nB+B))=O(q\log(w)\dfrac nB\log B+qB)$，一般近似地认为 $\log w$ 和 $\log B$ 同阶。取 $\sqrt{n}\log w$ 以平衡时间复杂度。
二分时可以使用分散层叠减少二分次数，达到 $O(q\sqrt n)$ 的时间复杂度。
见 gxy001 的博客。
物品成序列，每次对其中的一个区间做背包问题。
设一组物品 $S$ 限定体积不超过 $m$ 的情况下能够取得的最大价值为 $f_S(m)$。如果使用线段树维护区间内元素的 $f_S$ 值会带来大量复杂度为 $O(m^2)$ 合并。而插入单个元素时间复杂度为 $O(m)$，所以我们倾向于使用更多的插入操作而非合并操作。
考虑对区间进行分治，将每个询问放到最小的完全包含询问区间的分治区间进行处理。显然询问区间一定跨过该分治区间中点。于是对于每个分治区间，预处理其前半部分的每个后缀的 $f$、后半部分的每个前缀的 $f$，各 $O(nm)$ 的时间复杂度，然后对所有跨过区间中点的询问，进行一次 $O(m)$ 的合并（因为这里只需要算出 $f$ 的一处点值）即可求得答案。
复杂度为 $O(nm\log n+mq)$
一种做法是，为等价类（颜色）寻找代表元，即待统计区间中最靠后者。
然后将询问按照右端点排序，保证统计区间为一个前缀。
如果区间中存在某种颜色，那么这种颜色的代表元一定在区间中，于是用树状数组维护当前前缀代表元数目，单点改、区间求和即可。
另一种做法：区间二维数点
对于数列中某个位置 $i$，记 $p_i$ 为 $i$ 之前最后一个颜色与 $i$ 相同的位置。
于是我们所求的，区间颜色数量，等价于求满足 $i\in[l,r],p_i<r$ 的位置数量。即代表元数量。
直接扫描线。
从节点 $0$ 出发，在无向图上游走，在每个节点有 $p$ 的概率终止，否则等概率走向相邻节点。
设 $f_{i,u}$ 为 $i$ 时刻之前随机游走过程未终止，而 $i$ 时刻小 P 在点 $u$ 的概率。
而 $0$ 时刻在点 $1$，于是 $f_{0,u}=[u=1]$。
而第 $i$ 时刻（$i>1$）的情况可以表示为
$$\displaylines{f_{i,u}=\sum_{v\in N(u)}\frac{(1-p)f_{i-1,v}}{|N(v)|} }$$于是最终停留在点 $u$ 的概率为
$$\displaylines{\sum_{i=0}^\infty pf_{i,u}=p\sum_{i=0}^\infty f_{i,u} }$$令
$$\displaylines{\begin{aligned} g_u&=\sum_{i=0}^\infty f_{i,u}\\ &=f_{0,u}+\sum_{i=1}^\infty f_{i,u}\\ &=f_{0,u}+\sum_{i=1}^\infty\sum_{v\in N(u)}\frac{(1-p)f_{i-1,v}}{|N(v)|}\\ &=f_{0,u}+\sum_{v\in N(u)}\sum_{i=1}^\infty\frac{(1-p)f_{i-1,v}}{|N(v)|}\\ &=f_{0,u}+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\sum_{i=0}^\infty f_{i,v}\\ &=f_{0,u}+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\cdot g_v \end{aligned} }$$据此我们可以列出关于 $g$ 的方程组
$$\displaylines{\begin{cases} g_0+\sum_{v\in N(0)}\frac{1-p}{|N(v)|}\cdot g_v=1\\ g_u+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\cdot g_v=0&(u\neq 0) \end{cases} }$$然后使用高斯消元求解。
从节点 $0$ 出发，在无向图上游走，等概率走向相邻节点，到 $t$ 点结束，求经过每条边的期望次数。
记 $N'(u)=N(u)\setminus\{t\}$。
设事件 $A_{i,u}$ 为第 $i$ 个时刻在点 $u$，$B_{i,v,u}$ 为 $i-1$ 时刻到 $i$ 时刻间由点 $v$ 转移到了点 $u$。显然有 $P(A_{0,u})=[u=0]$。
不难发现，对于 $v\in N'(u)$ 有
$$\displaylines{P(A_{i,u}B_{i,v,u})=P(A_{i-1,v}B_{i,v,u})=P(B_{i,v,u}|A_{i-1,v})P(A_{i-1,v})=\frac{P(A_{i-1,v})}{|N'(v)|} }$$由全概率公式，易得
$$\displaylines{P(A_{i,u})=\sum_{v\in N'(u)}P(A_{i,u}B_{i,v,u})=\sum_{v\in N'(u)}\frac{P(A_{i-1,v})}{|N'(v)|} }$$设 $f_u$ 为经过 $u$ 的期望次数，由期望的线性性可得
$$\displaylines{\begin{aligned} f_u&=\sum_{i=0}^\infty P(A_{i,u})\\ &=P(A_{0,u})+\sum_{i=1}^\infty\sum_{v\in N'(u)}\frac{P(A_{i-1,v})}{|N'(v)|}\\ &=[u=0]+\sum_{v\in N'(u)}\sum_{i=0}^\infty\frac{P(A_{i,v})}{|N'(v)|}\\ &=[u=0]+\sum_{v\in N'(u)}\frac{f_v}{|N'(v)|} \end{aligned} }$$由此可列出线性方程组，通过高斯消元解得答案。