Luogu4156 [WC2016] 论战捆竹竿

发表于 分类于 ， ， 阅读次数：

题意：给出长为 的字符串 。对于字符串 ，若 覆盖 ，则称 是好的。求长度 的好的字符串的长度种类数。

多组数据，，，，时限 。

记周期为 。初始时串为 ，对于周期 ，可以复读 次，将长度加长 。全体好串的长度集合是 题目相当于问 中小于等于 的数的个数。

选择其中一个周期 为模数，设 则 ，这种表示称作“同余分类”。答案为 这将问题转化为 个点的最短路。但边数仍很多（周期数目），无法承受。

根据 Border 理论，周期具有特殊结构，它的长度可以被划分为 个等差序列。

处理单个等差数列：考虑 恰为 的情况。选择 作为模数，则图具有特殊结构，可以快速计算。

具体地，模 意义下只剩 一类同余步长，会形成 个互不相干的环，对于每个环分别处理。

在单个环上，每个点只能从前 个点过来，而 之间的边长是 。容易发现，环上 最小的点不会被更新，从该点出发顺时针更新即可。按照 使用单调队列维护长度为 的滑动窗口，时间复杂度 。

转换同余分类的模数：假设我们现在持有集合 ，它被表示为模 的同余分类，即 我们要加入变量 ，即向 中加入 的若干倍 我们希望将新的 表示为模 的同余分类。

首先令 ，然后，每个位置还可以任意地 ，再次分环跑同余系最短路即可。不过，此时没了 的范围限制，所以一路取 就行。

将以上两个步骤结合起来，等差数列只有 个，复杂度 。