双模数结构、周期引理和同余最短路
Published:
提示：本文和双模数 hash 没有关系。
双模数结构
给出正整数 $p,q,T$ 和整数集 $A,B$，请你求出：
\[\sum_{i=0}^{T-1}[(i \bmod p) \in A \land (i \bmod q) \in B]\]$p,q \le 10^6$，$T \le 10^{18}$。
我们不关心这题的具体做法，只讲怎么刻画条件。怎么处理 $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 和双模数结构的强关联。
- 弱周期引理 Weak Periodicity Lemma (WPL)：$p$ 和 $q$ 是 $S$ 的 period 且 $p + q \le \lvert S \rvert$，则 $\gcd(p, q)$ 也是 $S$ 的 period。
- 周期引理 Periodicity Lemma (PL)：$p$ 和 $q$ 是 $S$ 的 period 且 $p + q - \gcd(p, q) \le \lvert S \rvert$，则 $\gcd(p, q)$ 也是 $S$ 的 period。
- $p + q - \gcd(p,q)$ 这个下界是紧的，无法继续加强，$\lvert S \rvert$ 再小就有反例了。
证明
像并查集一样，连边 $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 对应的图。
双模数同余最短路
给定正整数 $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。
多模数同余最短路
多模数没有双模数的优秀性质了，建出的图很乱。
给定 $x,y,z$，求出 $[1,n]$ 中有几个数可以被表示成 $ax+by+cz$（$a,b,c \ge 0$）的形式。
$x,y,z \le 10^5$，$n \le 2^{63} - 1$。
在 $\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}$。
写在后面
- 文章完工了我才知道 CF1205E Expected Value Again 的题解区有我刚才构造的关于 PL 的所有东西。哈哈哈。