同余最短路

定义

假设我们在非负整数集下讨论问题。

从一个自然的问题出发：给定一个正整数集合 \(S=\{s_1,s_2,\cdots, s_n\}\)，再给你一个数 \(t\)，如何判定 \(t\) 能否被 \(S\) 中的数线性表出？也就是，是否存在一组整数 \(k_1,k_2,\cdots, k_n\)，使得

\[ t=\sum_{i=1}^{n}k_is_i \]

显然，这个问题是背包。

但如果 \(S\) 的数都不太大，但 \(t\) 是一个很大的数呢？

考虑以 \(S\) 中的某一个数为基准，不妨记它为 \(b\)，那么所有整数肯定都能被表示为

\[ bk+r \]

的形式。

假设 \(r_1,r_2\) 都可以被其他整数表示出来，\(r_1<r_2\) 且 \(r_1\equiv r_2\pmod{b}\)，那么肯定有 \(r_2=r_1+bz\)，所以我们对于每个模 \(b\) 的同余类 \(\overline r_b\)，只用关心最小的那个能被表示出的 \(r\)。

显然，这是一个模意义下完全背包。

设 \(f_x\) 表示模 \(b\) 意义下等于 \(x\)，能够被表示出来的最小的数。

有一些方法计算这个东西的时候用到的是最短路之类的东西，我们不这样干，考虑转圈。

我们知道，从对于一个 \(0\sim a\) 的序列，令每个点 \(i\) 向 \(i+m\bmod a\) 连边（实际上刻画的是每次往后跳 \(m\) 步），整个图形成 \(\gcd(a,m)\) 个环，每个环的长度是 \(\frac{a}{\gcd(a,m)}\)，这是经典的，具体见 P6187 的题解。

这里说到了一个问题就是，实际上对于每个 \(i\)，能转移到它 / 被它转移到的点恰好构成了一个环。

但是肯定不会在这个环上无穷地转下去，这样的情况必然是代价为负（负环），事实上，转恰好两圈就行了。

转移成环的问题在于，每个 \(x\) 更新了后面的一组值，这可能更新到原先转移其他点 \(z\) 用的那个点 \(y\)，更新这个点后 \(z\) 要被重新更新（转第二圈）。

考虑为什么只需要更新两次，这是因为我们的转移为 \(f_x\leftarrow \min(f_x,f_y+w)\)，这相当于用三角形不等式 \(f_y\le f_x+w\) 更新每个环上的点，而边权非负的最短路不会经过一个点两次。

模板题 / P2371. 墨墨的等式

给你 \(n\) 个 \(a_i\)，求 \([l,r]\) 中有多少个数 \(b\) 可以被表示成

\[ b=\sum_{i=1}^{n}a_ix_i \]

的形式。其中 \(x_i\ge 0\)。

\(n\le 15,0\le a_i\le 5\times 10^5,1\le l,r\le 10^{12}\)

Solution

随便选一个 \(m\)，考虑用同余最短路求出每个 \(0\le i<m\) 最小的 \(f_i\)，然后计算 \([l-f_i,r-f_i]\) 中 \(\ge 0\) 的 \(m\) 的倍数个数即可。

代码见这里。