自动搬运

查看原文

来自洛谷，原作者为

	時空 挂分领域代师

搬运于2025-08-24 23:04:35，当前版本为作者最后更新于2024-10-03 22:57:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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]$ 不“无趣”。

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

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

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