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)\) 多了亿点常数。
由于离线,可以分治。
谁想写这个毒瘤的代码啊!