题解：CF1110H Modest Substrings

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

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

这为啥是对的？

当 $|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$ 时统计。