约束
tar[x][c]：SAM 转移
pre[x]：常用名有 link、fail 等 （反正就那个东西）
len[x]：结点 x 代表的最长字符串的长度
广义后缀自动机（下文用广义 SAM 指代），即用多个字符串的后缀建出的一个后缀自动机，拥有和后缀自动机相似的性质。
有三种较流传广泛的广义后缀自动机写法：
起因
一个偶然的机会让我发现自己平时一直用的快读模板甚至没有 scanf 快
![[题解] [HNOI2008] Cards](/image/abandoned_relics.jpg)
给你 $n$ 张牌要求染成红、蓝、绿三种颜色（求染出 $S_r$ 张红色，$S_b$ 张蓝色，$S_g$ 张绿色），并给定了 $m$ 种洗牌方案，这些洗牌方案满足：
- 任意多次洗牌都可用这 $m$ 种洗牌法中的一种代替
- 对每种洗牌法，都存在一种洗牌法使得能回到原状态
问有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。
$m\le 60$，$\max{S_r,S_b,S_g}\le20$
![[题解] [SCOI2010] 序列操作](/image/village.jpg)
要求构造一个满足 $m$ 个条件的 $n$ 项多项式，每个条件形如多项式在某个点取值为正/负。
$1\le n\le 32$，$1\le m\le 4000$
一个序列，多组询问，每次询问给出 $l$ 和 $q$，问：
$$
\sum_{i=l}^{l+q-1}\max_{l\le j\le i}a_j
$$强制在线。
$1\le n,m\le 5\cdot 10^5$
什么是 $NTT$
就是把把 $FFT$ 中所有的单位根换成了整数的单位根，也就是原根的 $n$ 次幂
通常用于求模意义下的多项式卷积
在上一篇文章里面我们介绍了 $FFT/IFFT$ 的基本原理和应用，今天我们来了解一下 $FFT$ 在字符串匹配中的神奇应用
引入问题
什么是多项式卷积
假设我们现在有多项式 $f(x)$ 和 $g(x)$ ，它可以被表示为
$$
f(x)=\sum_{i=0}^{n-1} a_i\cdot x^i\\
g(x)=\sum_{i=0}^{m-1} b_i\cdot x^i
$$
其中 $a$ 和 $b$ 为系数数组， $n$ 和 $m$ 分别为两个多项式的长度
那么它们的卷积为
$$
f(x)\bigotimes g(x)=\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i\cdot b_j\cdot x^{i+j}
$$
也可以表示成
$$
c_k=\sum_{i=0}^ka_i\cdot b_{k-i}
$$
其实就是简单的两个多项式相乘
