P2371 [国家集训队] 墨墨的等式 分析 & 同余最短路

· · 个人记录

$$a_k\cdot (x_i+1) + \sum\limits_{i=1, i \neq k}^na_ix_i=b+a_k$$ 实际上，我们并不需要考虑每一个 $b$，只需要考虑其在 $\mod a_k$ 意义下的情况。因为对于所有 $b \gt a_k$，我们都可以设 $b' = b - a_k$，此时有： $$a_k\cdot (x_i-1) + \sum\limits_{i=1,i\neq k}^n a_ix_i = b - a_k$$ 即，若有 $b \ge a_k$ 可以满足这个不等式，一定可以找到 $b' \in \mod a_k$ 满足这个不等式。 于是我们设 $f(x)$ 代表在 $[x]$ 内满足此不等式的最小值，那么 $f(x) = \min\limits_{i=0}^n f(x - a_i) + a_i$。这和最短路的松弛操作很像。于是我们可以用最短路来做。 求出所有的 $f(x)$ 后，统计根的数量即可。 不得不说这题作为紫的确有点水了，说不定以后会和数位 DP 一样降绿（）