双模数结构、周期引理和同余最短路

· · 算法·理论

提示：本文和双模数 hash 没有关系。

双模数结构

P5330 [SNOI2019] 数论

给出正整数 p,q,T 和整数集 A,B，请你求出：

\sum_{i=0}^{T-1}[(i \bmod p) \in A \land (i \bmod q) \in B]

我们不关心这题的具体做法，只讲怎么刻画条件。怎么处理 x \bmod p 和 x \bmod q 同时出现的式子？

考虑固定 x \bmod q。对于 [0,q) 每个数建一个点，每个点 i 连边到 (i + p) \bmod q，则可以证明：整张图是 \gcd(p,q) 个环，每个环环长为 \frac q {\gcd(p,q)}。

通过这样的结构，我们可以把二维的双模数问题，转化为 \bmod q 下的一个环上问题。

WPL 与 PL

弱周期引理 WPL 和周期引理 PL 都是字符串题目中常见的套路。并且这篇文章后面的部分揭示了 PL / WPL 和双模数结构的强关联。

证明

像并查集一样，连边 i \to i+p 和 i \to i+q。但是直接这么考虑不太行。

学习上面的思路，在 \bmod q 下看待这个问题，即我们合并所有 \bmod q 下相等的点。此时 i \to i + q 的边天然成立了；剩余每条边形如 i \to (i + p) \bmod q。

一开始有 q 个点，最后要连成 \gcd(p,q) 个连通块，至少要连 q - \gcd(p,q) 条边。我们已经证明过了最终是个环结构，因此每条边都不浪费（浪费的定义是，一条边连的两点早就连通了）。

我们连的最后一条边在原图上对应的是 q - \gcd(p,q) \to p + q - \gcd(p,q)。因此对于 PL，最小的字符串长度是 p + q - \gcd(p,q)。这也说明了为什么这个界是紧的，因为更少的边根本没办法让连通块只剩 \gcd(p,q) 个。

PL 对应的图上，每个本应该是环的连通块事实上缺了一条边，每个连通块都是一条链。若再多花 \gcd(p,q) 条边，即字符串长度达到 p+q 时，每个连通块被补全成为完整的环。这也就是 WPL 对应的图。

双模数同余最短路

P3951 [NOIP 2017 提高组] 小凯的疑惑

给定正整数 p,q，保证 p \perp q 且 p,q \ge 2。求不能被表示为 xp+yq（x,y \ge 0）的最大正整数。

我们在 \bmod q 下看。连边 i \to (i+p) \bmod q 权值 p。0 号点到每个点 i 的单源最短路 dis_i，即为 \bmod q 下所有可以拼出的数的最小值，比它大的 dis_i + kq（k \ge 0）都可以拼出。

而根据前面的结论，这张图形成一个环，最远的点是走 q-1 步走到的点 p (q-1) \bmod q，最短路为 p (q-1) = pq - p，即这个同余类中可以表示出的最小值是 pq-p。

因此，表示不出的最大数要再减 q，是 \boxed{pq - p - q}。这个结论在国外被称为 Chicken McNugget Theorem。

多模数同余最短路

多模数没有双模数的优秀性质了，建出的图很乱。

P3403 跳楼机

给定 x,y,z，求出 [1,n] 中有几个数可以被表示成 ax+by+cz（a,b,c \ge 0）的形式。

在 \bmod x 下看，连边 i \to (i + y) \bmod x 边权 y 和 i \to (i + z) \bmod x 边权 z。一样的最短路，使用 Dijkstra 在 O(x \log x) 的时间求解。

小技巧：由于 x,y,z 对称，选择一个最小的作为模数，可以减小常数。

2023 AMC 12B Problems/Problem 16

In the state of Coinland, coins have values 6,10, and 15 cents. Suppose x is the value in cents of the most expensive item in Coinland that cannot be purchased using these coins with exact change. What is x?

在 \bmod 6 下看，连边 i \to (i + 10) \bmod 6 边权 6 和 i \to (i + 15) \bmod 6 边权 15。模拟 Dijkstra 可以算出最长的最短路是 35，35 - 6 = \boxed{29}。

写在后面

练习题