同余最短路

不整东西还是遗忘的快啊……

同余最短路大概是鼓励你把 $\text{dp}$ 的某一维改成同余意义下，然后通常转移就成环了，然后你就顺理成章的用最短路来解决。

首先这得是个最优化问题。

来看几个套路吧：

超大容量背包

求出多少 $b\in[l,r]$ 满足方程 $\sum_{i=1}^na_ix_i=b$ 存在非负整数解。

$n\le 12,0\le a_i\le 5\times 10^5,l,r\le 10^{12}$ 。

也就是要用若干个 $a$ 来凑出 $b$ 即可。

对 $a$ 的一个完全背包。

我们考虑任意找一个 $a_1$ 为基准量，在 $\bmod \ a_1$ 的意义下，我们跑一个 01bfs 来凑数。

感觉很对吧，但是你发现在 $\bmod \ a_1$ 的意义下实际上会出现用了负数个 $a_1$ 的情况。

所以我们不能用 0/1 当状态，用“这个值至少得是多少”来当状态，然后就完美的解决了。

完全背包，但物品有体积和价值，求凑出 $V$ 体积的最大价值。

$V\in[10^{11},10^{12}],v_i\le 10^5,n\le 50$ 。

上题的基础上多一维肯定复杂度接受不了了，但我们可以规避掉上述问题。

找到性价比最高的物品，以它为基准物品，可以证明最终答案一定要选正数个该物品。

在多绕一圈的时候需要减掉该物品的价值。