CodeChef YANSPP 官方题解翻译

使用 DeepSeek 进行翻译。

YANSPP - 题解

题目链接：

竞赛 - 三级组别
竞赛 - 二级组别
竞赛 - 一级组别

难度：

中等-困难

前置知识：

0-1广度优先搜索，全源最短路径，模幂运算

题目描述：

给定一个整数 \(K\) 和一个包含 \(P\) 个节点的图，其中 \(P\) 为质数。对于每个顶点 \(u\)，都存在一条从 \(u\) 到 \((K\cdot u+i)\mod P\) 的有向边，边权为 \(i\)，其中 \(0\le i\le K-1\)。

给定 \(Q\) 次查询，每次询问两个节点间最短路径的长度（若路径存在）。

题目解析：

我们首先处理 \(K\equiv 0\mod P\) 的简单情况。

解法

从节点 \(u\) 出发的边权为 \(i\) 的边指向节点 \((K\cdot u+i\mod P) = (i \mod P)\)（对所有 \(u\) 均成立）。因此，每条指向节点 \(v\) 的边的边权均为 \(v\)（若两个节点间存在多条有向边，仅考虑边权最小的那条）。

由于所有节点对之间均存在有向边（因为 \(K\ge P\)），总是可以从 \(X\) 到达 \(Y\)，成本为 \(Y\)。因为所有指向节点 \(Y\) 的边的边权均为 \(Y\)，所以从 \(X\) 到 \(Y\) 的最小成本为 \(Y\)。

现在我们仅考虑 \(K\not\equiv 0 \mod P\) 的情况。

设 \(G\) 表示从原图中移除所有权值非零的边后形成的图。我们能在 \(G\) 中发现哪些有趣的性质？

图形直观

下图展示了由初始图构建的 \(G\)（参数为 \(K=8, P=13\)）。

我们可以观察到两个有趣的性质：

• 该图由多个循环分量组成
• 每个循环分量的长度相同（除了仅包含节点 \(0\) 的分量）

这些观察的证明如下（虽然这些性质的含义可能并不明显，但它们构成了解决方案的关键部分！）

断言： 图 \(G\) 由（可能多个）有向循环子图组成，且每个循环的长度相同（除了仅包含节点 \(0\) 的子图）。

证明

容易推断，在图 \(G\) 中，不存在指向节点 \(0\) 的入边或从节点 \(0\) 出发的出边。

对于所有其他节点 \(u\)，从节点 \(u\) 出发的唯一出边指向节点 \((K\cdot u\mod P)\)。因此，\(G\) 中的节点按以下方式链接：

\[u\to (K\cdot u\mod P)\to (K^2\cdot u\mod P)\to \dots \]

由于 \(K\) 和 \(P\) 互质，模幂运算的性质表明上述方程中的值是循环的。显然，循环的长度等于最小的正整数 \(R\)，使得：

\[ K^R\cdot u\equiv u\mod P\implies K^R\equiv 1\mod P \]

因此，每个节点 \(u\ (u\ne 0)\) 属于一个长度为 \(R\) 的循环子图。

回顾： 设 \(R\) 为 \(G\) 中循环子图的长度，则 \(K^R\equiv 1\mod P\)。

---

我们回到原图。

断言： 任意两个节点之间的最短路径可以仅通过边权为 \(0\) 和 \(1\) 的边实现。

证明

对于任意边 \(u\to (K\cdot u+i\mod P)\)，我们证明可以使用仅包含边权为 \(0\) 和 \(1\) 的路径，以相同的总成本 \(i\) 从节点 \(u\) 到达 \((K\cdot u+i\mod P)\)。

考虑一个非负整数数组 \(\{a_1, a_2, \dots, a_i\}\)，使得从节点 \(u\) 出发：

• 经过一次出边（边权为 \(1\)），然后经过 \(a_1\) 次出边（边权为 \(0\)）
• 再经过一次出边（边权为 \(1\)），然后经过 \(a_2\) 次出边（边权为 \(0\)）
• 依此类推（总共进行 \(i\) 次迭代）

此方式行驶的总成本等于 \(i\)。终点节点可由以下方程描述：

\[K^{a_i}(\dots(K^{a_2+1}(K^{a_1+1}(K\cdot u+1)+1)+1)\dots+1)\mod P \]

剩下的工作是找到合适的 \(a_i\)，使得我们最终到达节点 \((K\cdot u+i\mod P)\)。可以简单验证，设置 \(a_x=R-1\ (x<i)\) 且 \(a_i=R\) 可使上述方程等于 \(K\cdot u+i\)。

因此，任何使用边权为 \(i\) 的边的最短路径都可以被一系列仅包含边权为 \(0\) 和 \(1\) 的边替代，且总成本不变。

现在问题大大简化了，图中需要考虑的边总数减少到 \(2\times P\)。然而，由于节点数量庞大，计算任意两节点间的最短路径仍然不可行。

这时我们利用最初描述的 \(G\) 的性质！

情况 1：

如果 \(G\) 中的循环数量（等于 \(\frac{P-1}{R}\)）较小，我们可以将原图中属于 \(G\) 的同一循环子图的所有节点合并为一个节点（因为我们可以仅通过边权为 \(0\) 的边在这些节点之间移动）。

然后，在此压缩图上运行 Floyd-Warshall 算法，以获取任意两个组件之间的最短距离（这可用于查找原图中任意两个节点之间的最短距离）。

当 \(\frac{P-1}{R} \le 500\) 时，此方法效果良好。该方法的时间复杂度为：

\[O\big(P+\bigg(\frac{P-1}{R}\bigg)^3\big) \]

每个测试用例。

情况 2：

当 \(G\) 中的循环数量很大时，压缩图（如前一情况所述）仍然有太多节点，无法在时间限制内计算图的全源最短路径（APSP）。显然，我们需要一种不同的方法。

符号说明： 设 \(d(x,y)\) 表示从节点 \(x\) 到 \(y\) 的最短路径长度。

符号说明： 设 \(Z_X\) 表示 \(G\) 中与节点 \(X\) 属于同一循环子图的所有节点的集合。即 \(Z_X=\{K^i\cdot X\mod P\ \forall\ i\in\N\}\)。

断言： \(d(X,Y)=\min_{X'\in Z_X} d(0,(Y-X' \mod P))\)

证明

定义 \(f(u, s)\) 为路径的终点节点：

• 从节点 \(u\) 开始
• 路径长度等于（二进制）字符串 \(s\) 的长度
• 路径中第 \(i^{th}\ (1\le i\le |s|)\) 条边的权重为 \(s_i\)

解释

考虑 \(K=8,P=13\) 的图。设 \(u=2,s=1001\)。则路径中访问的节点序列如下：

\[2\to_{1} 4\to_{0} 6\to_{0} 9\to_{1} 8 \]

其中 \(\to_{i}\) 表示权重为 \(i\) 的边。
因此 \(f(u,s)=8\)。

我们证明对于任意 \(S\)，\(f(X, S)=Y\) 当且仅当 \(f(0,S)=(Y-X'\mod P)\)，其中 \(X'\in Z_X\)。证明这一点等价于证明原断言。

这如何证明原断言？

假设上述断言成立。

那么，如果 \(s\) 是某个从 \(X\) 到 \(Y\) 的最短路径的移动序列，它也是一个移动序列，使我们从节点 \(0\) 到达 \((Y-X'\mod P)\)（对于某个 \(X'\)）。

由于路径的成本仅取决于 \(s\)（确切地说是 \(s\) 元素的和），上述陈述意味着：

\[d(X,Y)\ge d(0,(Y-X'\mod P)) \]

对于某个 \(X'\in Z_X\)。

类似地，该陈述的逆意味着：

\[d(0,Y-X')\ge d(X,Y) \]

对于所有 \(X'\in Z_X\)。

结合两个陈述，我们得到：

\[d(X,Y)=\min_{X'\in Z_X} d(0,(Y-X' \mod P)) \]

从而证明了原断言。

容易看出 \(f(u,s)=K^\alpha\cdot u+\beta\mod P\)，其中常数 \(\alpha,\beta\) 仅由 \(s\) 决定。因此，

\[f(X,S) = K^\alpha\cdot X+\beta\equiv Y\mod P\\ \implies X'+\beta\equiv Y\mod P\\ \implies \beta\equiv Y-X'\mod P \]

那么，

\[f(0,S)=K^\alpha\cdot 0+\beta = \beta\\ \implies f(0,S) = Y-X'\mod P \]

该断言的逆可以类似证明。

利用这一关键性质，我们可以按以下方式解决问题：

• 首先，在线性时间内计算从节点 \(0\) 到所有其他节点的最短路径长度
• 然后，为了找到从 \(X\) 到 \(Y\) 的最短路径长度，通过遍历 \(R\) 个可能的 \(X'\) 值，计算 \(\min_{X'\in Z_X} d(0,(Y-X'\mod P))\)

此方法的时间复杂度（所有查询）为

\[O(P+Q\cdot R) \]

每个测试用例。

解决方案：

题解提供者的解决方案可见此处。