[WC 2016] 论战捆竹竿

果然字符串的终点和字符串没什么关系吗。

不难发现我们每次只会在一个长竹竿后面拼接一个基础的短竹竿来增加长度。假设每次拼接竹竿的重叠部分为 \(p\)，显然 \(p\) 是字符串的一个 border。

我们可以把这个字符串的所有 border 求出来，得到一个大小为 \(m\) 的集合 \(\{b_i\}\)。最后要求的就是满足 \(v\in [0,w-n]\)，且方程 \(\sum_{i=1}^m b_ix_i=v\) 存在解的 \(v\) 的数量。

好的，后面是一个经典的同余最短路问题，于是我们得到了一个 \(\min{b_i}\times n\) 的解法，但是这个做法是 \(O(n^2)\) 的。

考虑优化这个做法，经典结论是一个字符串的 border 可以划分成 \(\log n\) 段等差数列 \(d_i+c_il_i\)（结论证明较为复杂）。考虑对于每一个 \(i\)，求出在 \(\bmod d_i\) 意义下，加入前 \(i\) 个等差数列对应的边后的最短路。

依次加入每个等差数列，计算对最短路的影响。先考虑将原来 \(\bmod d_{i-1}\) 意义下的最短路换成 \(\bmod d_i\) 意义下的最短路，设前后两者对应的最短路数组为 \(f_i,g_i\)，可以用 \(f_i+kd_{i-1}\) 去更新 \(g_{(i+kd_{i-1})\bmod d_i}\)，其中 \(k\) 是没有限制的。

可以看成每个点 \(i\) 向 \((i+d_{i-1})\bmod d_i\) 连一条有向边，这样整个图显然会划分成 \(\gcd(d_{i-1},d_i)\) 个环，每个环之间独立。这样就很好做了，断环成链复制一遍，然后用环上上一个位置更新当前位置，总复杂度 \(O(n)\)。

转化完模数后，考虑用 \(g_{i}+kc_i\) 去更新 \(g_{(i+kc)\bmod d_i}\)，其中 \(k\in [0,l]\)，还是可以看成每个点 \(i\) 向 \((i+c)\bmod d_i\) 连一条有向边，划分成 \(\gcd(d_i,c)\) 个环，但只能转移一次，最多从前 \(l\) 个位置转移，单调队列 \(O(n)\) 即可。

这样时间复杂度为 \(O(Tn\log n)\)。