论战捆竹竿
题意:给定字符串 \(s\),计数 "串 \(t\) 的长度" 可能的种数有多少种,使得 \(t\) 能被 \(s\) 作为印章印出来,且 \(|t|\le w\)。\(n=|s|\le 5\times 10^5\),\(n\le w\le 10^{18}\)。
第一步:
求出 \(s\) 的周期 \(\{a_1\sim a_m\}\),包含 \(n\)(\(a_m=n\))。转化为求 \(\sum a_ib_i\le w-n\) 的情况下,\(\sum a_ib_i\) 的取值有多少种,要求 \(b_i\ge 0\)。记 \(w_0=w-n\)。
第二步:
\(\sum a_ib_i\) 的形式,考虑同余最短路。(当题目中出现类似 "若干个数求和" 的形式,可以考虑同余最短路)
记 \(A=\min a_i\),令 \(F_i\) 表示 \(\bmod A=i\) 的所有数中,能表示为 \(\sum a_ib_i\) 的最小数是多少。
如果这里直接跑最短路,一共有 \(A\) 个点,每个点通过 \(a_1\sim a_m\) 都会连出 \(m\) 条边,所以复杂度至少是 \(O(A\cdot m)\) 的。同时可以构造出来 \(s=aaa\dots abaa\dots aaa\),使得周期数量达到 \(O(n)\) 个,同时周期的长度都是 \(\ge n/2\) 的,肯定能被卡。
第三步:
我们需要改进这个方法。根据 border 理论,\(\{a_1\sim a_m\}\) 可以被分成 \(\log n\) 个等差数列。
把每个等差数列单独拎出来,依次考虑。
考虑第 \(k\) 个等差数列 \(\{x,x+d,x+2d,\cdots,x+td\}\),构造 \(x\) 个点编号 \(0\sim x-1\)。\(F(i)\) 表示如果使用前 \(k-1\) 个等差数列中的数,它们能组成的数中,\(\bmod x=i\) 的最小数是多少。
我们要用 \(F(i)\) 推出 \(F_{new}(i)\):使用前 \(k\) 个等差数列中的数,它们能组成的数中,\(\bmod x=i\) 的最小数是多少。
首先把同余最短路的图建出来。观察发现,按照 \(gcd(x,d)\) 分类,每一类之间没有边,内部有边。于是我们把 \(\bmod gcd(x,d)\) 相等的一起处理。
也就是说,比如 \(gcd(x,d)=3\),先把 \(F(0),F(3),F(6),\dots\) 转移到 \(F_{new}(0),F_{new}(3),\dots\),然后再转移 \(F(1),F(4),\dots\) 和 \(F(2),F(5),\dots\),各自求解,然后拼出来 \(F_{new}\)。
如果还是把 \(\bmod gcd(x,d)\) 相等的点拿出来跑最短路,还是没有优化。这里有一个破环为链的 DP 想法。举个例子,比如当前等差数列是 \(\{15,24,33\}\),\(gcd(15,9)=3\),所以按 \(3\) 的余数分类。比如现在正在处理 \(F(1,4,7,10,13)\)。它们之间的边连出来应该是这样:
不妨 \(F(10)\) 是其中最小的点。我们以 \(10\) 这个点破环为链:只保留从前往后的边(不越界)。我们会证明,在这个链图上如果跑最短路,答案和环图是一样的。
证明:考虑到点 \(x\) 的最短路,假设破环为链的起点是 \(st\)。如果存在另一个点 \(y\),走了一条不存在的边使得 \(dist[x]\) 更短了。但是因为 \(st\) 是 \(F()\) 最小的,所以 \(F(st)<F(y)\);同时因为 \(y\) 走到 \(x\) 是越界的,所以 \(y\) 到 \(x\) 一定比 \(st\) 到 \(x\) 更远,根据等差数列的性质,\(st\) 一定存在一条比 \(y\rightarrow x\) 的边更短的。因为 \(F(st)<F(y)\),而且 \(st\) 出发还有更小的边,所以一定不会存在这样的 \(y\)。
因此我们只需要保留这个链图跑最短路。但是真的需要跑最短路吗?是可以优化的。
记链上第 \(i\) 个点的 \(F_{new}\) 值为 \(g_i\)(从 \(0\) 开始编号)。首先可以写出一个朴素的 DP 方程。
\(g_i=\min\{F(i),g[j]+x+(i-j)d|i-t\le j\le i-1,j\ge 0\}\)。这里 \(i-t\) 的 \(t\) 是上面 \(x+td\) 的 \(t\)。
这个式子很显然可以单调队列优化,于是复杂度从最短路和边数有关的复杂度,降低到 \(O(\text{点数})\)。
这一部分贡献的复杂度,对于每个等差数列会贡献 \(O(\text{点数})\) 的复杂度,一共 \(\log n\) 个等差数列,所以会贡献 \(O(n\log n)\) 的复杂度。
第四步:
第三步解决了从 \(F(i)\rightarrow F_{new}(i)\) 的问题,但是我们还需要让 \(F_{new}(i)\) 的模数变成第 \(k\) 个等差数列的 \(x\),而不是第 \(k-1\) 个等差数列的 \(x\)。例如当前模数(首项) \(x=15\),下一个等差数列模数(首项) \(x=12\)。怎么把 \(F(i)\) 的定义从 \(\bmod 15=i\) 的最小数,转化为 \(\bmod 12=i\) 的最小数,从而更方便用 \(\bmod 12\) 的 \(F(i)\) 推出属于 \(x=12\) 的 \(F_{new}(i)\)?
把 \(\bmod 15\) 的 \(F\) 记作 \(F(i)\),\(\bmod 12\) 的 \(F\) 记作 \(F'(i)\)。新的模数记作 \(x'\)。
这里 \(F'(i)\) 的更新取值分两种。
借一个具体的例子,比如 \(F(13)=28\)。
第一种:因为 \(28\bmod 12=4\),所以我们知道 \(F'(4)\) 可以取到 \(28\)。也就是如果 \(F(a)=b\),那 \(F'(b\mod x')\leftarrow b\)。
第二种:在 \(F\) 里 因为 \(F(13)=28\),所以 \(28+15\omega(\omega\ge 0)\) 都可以取到。在 \(F'\) 里对应着我们会用 \(F(13)+(15\bmod 12)\omega\) 去更新 \(F'\)。
考虑 \(F'\) 的更新建成同余最短路的图,实际上每个点只向后方第 \(3\) 个点连边。
理解一下。这里 \(F'\) 的同余最短路的建图和第三步的建图是不同的——\(F'\) 只有一种边,就是向后走 \(15\bmod 12=3\) 步的边。而第三步的建图有 \(\{x,x+d,\dots,x+td\}\) 一共 \(t+1\) 种向后走的边。所以 \(F'\) 的建图实际上就是一个环。
顺理成章地,沿用上面破环为链的想法。找到 \(\bmod 15\) 的所有 \(F(i)\) 里最小的,记作 \(F(mn)\)。以 \(mn\) 号点为起点破环为链,得到一条 \(mn\rightarrow mn+15\bmod 12\rightarrow mn+2\cdot (15\bmod 12)\rightarrow\cdots\) 的链,然后在这条链上走一遍,也就是 \(F'(mn+\alpha(15\bmod 12))\leftarrow F(mn)+15\alpha\)。
切换一次模数的复杂度是 \(O(\text{点数})\) 的。一共切换 \(\log n\) 次,也是 \(O(n\log n)\)。
总共 \(O(n\log n)\)。
标签:12,15,题解,bmod,论战,P4156,new,短路,等差数列 From: https://www.cnblogs.com/FLY-lai/p/18537078