同余最短路
当出现形如“给定 n 个整数,求这 n 个整数能拼凑出多少的其他整数(n 个整数可以重复取)”,以及“给定 n 个整数,求这 n 个整数不能拼凑出的最小(最大)的整数”,或者“至少要拼几次才能拼出模 K 余 p 的数”的问题时可以使用同余最短路的方法。
同余最短路利用同余来构造一些状态,可以达到优化空间复杂度的目的。
类比 差分约束 方法,利用同余构造的这些状态可以看作单源最短路中的点。同余最短路的状态转移通常是这样的 f(i+y) = f(i) + y,类似单源最短路中 f(v) = f(u) +edge(u,v)。
例题¶
例题一¶
P3403 跳楼机
题目大意:给定 x,y,z,h,对于 k \in [1,h],有多少个 k 能够满足 ax+by+cz=k。(1\le x,y,z\le 10^5,h\le 2^{63}-1)
不妨假设 x < y < z。
令 d_i 为只通过 操作 2 和 操作 3 能够达到的最低楼层 p,并且满足 p\bmod x=i。
可以得到两个状态:
-
i \xrightarrow{y} (i+y) \bmod x
-
i \xrightarrow{z} (i+z) \bmod x
注意通常选取一组 a_i 中最小的那个数对它取模,也就是此处的 x,这样可以尽量减小空间复杂度(剩余系最小)。
那么实际上相当于执行了最短路中的建边操作:
add(i, (i+y) % x, y)
add(i, (i+z) % x, z)
接下来只需要求出 d_0, d_1, d_2, \dots, d_{x-1},只需要跑一次最短路就可求出相应的 d_i。答案即为:
加一是由于当前所在楼层也算一次。
参考实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
|
例题二¶
ARC084B Small Multiple
题目大意:给定 n,求 n 的倍数中,数位和最小的那一个的数位和。(1\le n\le 10^5)
本题可以使用循环卷积优化完全背包在 O(n\log^2 n) 的时间内解决,但我们希望得到线性的算法。
观察到任意一个正整数都可以从 1 开始,按照某种顺序执行乘 10、加 1 的操作,最终得到,而其中加 1 操作的次数就是这个数的数位和。这提示我们使用最短路。
对于所有 0\le k\le n-1,从 k 向 10k 连边权为 0 的边;从 k 向 k+1 连边权为 1 的边。(点的编号均在模 n 意义下)
每个 n 的倍数在这个图中都对应了 1 号点到 0 号点的一条路径,求出 1 到 0 的最短路即可。某些路径不合法(如连续走了 10 条边权为 1 的边),但这些路径产生的答案一定不优,不影响答案。
时间复杂度 O(n)。
习题¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用