P11140

· · 题解

In Luogu

好题啊。感觉绿有点虚高，上位黄应该是。

注意到 n \le 1.5 \times 10^7，所以只能有 \mathcal{O(n)} 的做法。

记 f_i 表示将前 i 个数进行划分的方案数。

则显然有 f_i = \sum{f_j}，其中 j 满足 j < i 且 [i,j] 不为无趣的字符串。

手玩一下第三个样例，发现一个很好的性质：不为无趣字符串的字符串长度不会超过 18。具体会不会更小，出题人的爆搜表明不会超过 9，这里不考虑。

那么就可以 \mathcal{O(n^2)} 了，瓶颈在于检查一个区间是否“无趣”。

要做到 \mathcal{O(n)}，检查必须是 \mathcal{O(1)} 的。那么进行预处理：记 L_i 表示以 i 为右端点，能向左扩展的最远点，满足区间 [L_i, i] 不“无趣”。

显然这个东西是单调的。若 [x,i] 不“无趣”，则对于任意 x \le k \le i，区间 [k,i] 均不“无趣”。

那么双指针预处理即可。每次右端点 r 右移时，加入 r 的贡献，即将 [l,r],[l+1,r], \cdots, [r-1,r] 的和加入，如果其中有出现过的（即 [l,r] “无趣”），就左端点 l 不断右移，并删除 l 的贡献，直到没有重复出现的，即 [l,r] 不“无趣”。

判断是否重复出现可以开一个数组。那么就做完了。

注意有点卡常，把取模运算换成减法即可。

代码很丑，不放了。具体代码可以参考官方题解。