21.7.8 t1

tag:SAM,矩阵乘法,分治


首先我们要知道一个 trick,如何把两个 SAM 拼起来。

大概就是对于第一个 SAM 上的所有点,如果某个字符 \(c\) 没有出边,就连向第二个 SAM 的根结点的 \(c\) 出边指向的点。

这样最后会构造出来一个自动机,每一条路径都对应着一个题目中要求的字符串。(为了方便,可以倒着构造)


先考虑如何求 \(f(l,r)\)。

暴力就是直接从右往左 dp。

然后仔细观察会发现,第 \(i\) 个 SAM 的 dp 值,只与它的形态和第 \(i+1\) 个 SAM 的根的儿子的 dp 值有关。

也就是说 \(f[root_i]= a_1f[son[root_{i+1}][1]]+\cdots+a_Tf[son[root+{i+1}][T]]+1\)

所以可以用矩阵的形式,表示出第 \(i+1\) 个 SAM 的根的儿子,对第 \(i\) 个 SAM 的根的儿子的贡献,而矩阵只与第 \(i\) 个 SAM 的形态有关。

这个部分可以 \(O(nT^2)\) 求出来。(hehezhou说可以 \(O(nT)\),不过不重要)

于是可以 \(O(T^2logn)\) 的时间求出 \(f(l,r)\)。


然后要求 \(\sum_{l,r}f(l,r)\),相当于求一个类似于 \(\sum_{l,r}\prod_{i\in[l,r]}A_i\) 的东西。

再多维护一点东西就行了,所以实际上只是比求 \(f(l,r)\) 多了亿点常数。

由于离线,可以分治。


谁想写这个毒瘤的代码啊!

上一篇:[八省联考2018]制胡窜 (SAM+大讨论)


下一篇:电子数据取证时间取证读书笔记