题解：CF1110H Modest Substrings

· · 题解

这篇题解只是补充 AC 自动机题解里两个细节，前面推导请看其他题解。

经过推导，我们得到如下转移式：

f_{i+1,k}\gets f_{i,j}+\sum_{p=0}^{n-i-1}g_{k,p}

这为啥是对的？

不是说不能统计有前导 0 的串的贡献吗，为啥可以直接不考虑，或者直接就把长度在 [|l|+1,|r|-1] 的贡献单独统计了？

当 |r|-|l|\geq 2 时，0 只可能出现在低 |l| 位上，且这种情况出现还需要 l 中有 0。

笔者不会证。

感性理解就是，在中间含 0 亏了。尝试构造：选择位数为 |l| 或 |l|+1 的数作为循环。在位数一定，会选尽量小的循环节。

贡献是怎么统计对的？

在没缩满节点子树情况下，对于一满节点 j 到子树内一叶子，这些点到 fail 根路径上的 g 之和，就在 j 走 [i+1,i+d] 步到的状态统计。 具体来说，就是下面这幅图（j=1,d=3，虚线是跳 fail，c_{i} 是字符） 原本是 g_{2}+g_{3}+g_{4}+g_{5}+g_{7}+g_{8}。 压缩树后，g_{5}+g_{7}+g_{8} 在节点 1 走 fa_{1}\to 5\to 6\to 7\to 8 时统计。