再学同余最短路

__ryp__ · 2024-07-29 20:27:41 · 个人记录

P2371 为例。

我们可以取一个数 m \in A，然后设 f(k) 表示模 m 为 k 时整个式子最小值。

明显有 x 可以转移到 (x + a_i) \bmod m，权是 a_i。由于有后效性，我们不能直接转移，考虑最短路就可以跑出来。

然后我们可以把 [l, r] 差分成 [1, r] \cap [1, l - 1] 来统计答案。考虑怎么统计 [1, x] 的答案。如果 f(i) \le x，那么我们可以把 f(i) 加上任意个 x。所以解的数量就是 \dfrac{x - f(i) + 1}{x} + 1。

然后统计就行了。