选自 SDSC2024 Day1 数论选讲。

Descr

给定一个 $h\times w$ 的网格图，从左上角的点 $(0,0)$ 开始，你可以在每个格子选择往下或往右走，走出边界会循环，问哈密顿路径条数。

$h,w \leq 10^6$。

Sol

本题解分步讲解。因为较为抽象，建议读题解同时自己画图理解。

Observation #1

考虑“哈密顿路径”这一条件。

所谓哈密顿路径，就是不重不漏走每个点恰好一次的路径。

假设有一个点 $(x,y)$ 选择了往下走到 $(x+1,y)$，那么因为每个点只能走一次，所以 $(x+1,y-1)$ 就不能选择往右走到 $(x+1,y)$，只能选择往下走。

假设这个点 $(x,y)$ 选择了往右走，那么 $(x+1,y)$ 这个点只能从 $(x+1,y-1)$ 走过来，即从 $(x+1,y-1)$ 向右走，否则没有点能走到这里。

归纳下去，所有的左下-右上的对角线的方向的选择都相同。

再考虑“循环”这一条件。

假设有一个位于底部的点 $(h-1,y)$ 其选择了往下走到 $(0,y)$，那么 $(0,y-1)$ 就不能向右走，否则会重复走到一个点，所以要选择向下走。

假设其选择了向右走，那么因为 $(0,y)$ 位于顶端只能从 $(0,y-1)$ 走过来，那么 $(0,y-1)$ 也必须选择向右走。

剩余的位于顶部、左侧、右侧的情况也有类似规律。

上面所有规律的逆命题也成立。

对这个规律总结归纳，不难发现：

对于一个点 $(x,y)$，对于所有的 $k$，$((x+k)\bmod h,(y-k)\bmod w)$ 与 $(x,y)$ 选择的方向相同。

Observation #2

在上面的结论下，考虑有多少个本质不同的对角线。

假设有一个人，从一个点 $(x,y)$ 沿着对角线，走遍所有的 $k=0,1,2,\cdots$，容易发现他一定会回到 $(x,y)$。由上文的结论得，能使 $(x,y)$ 回到 $(x,y)$ 的 $k$ 一定满足：

$x+k\equiv x(\bmod h),y-k\equiv y(\bmod w)$。

进而可得 $h|k$ 且 $w|k$。

这样的最小的 $k$ 是 $\operatorname{lcm}(h,w)$。即每条对角线长度都为 $\operatorname{lcm}(h,w)$。

考虑一共有 $hw$ 个点，每条对角线有 $\operatorname{lcm}(h,w)$ 个点，那么一共有 $\frac{hw}{\operatorname{lcm}(h,w)}=\gcd(h,w)$ 条对角线。

令 $g=\gcd(h,w)$，也就是说我们只要确定这 $g$ 条对角线的方向就能确定整个方格图的方向。

Hint

正难则反，一共有 $2^g$ 种选择方向的方案，减去不是哈密顿路径的方案即为答案。

Observation #3

考虑一个不合法的方案是什么样的。

因为点数有限，每个点只有一个方向可走任意一个路径的选择，且不管怎么走都走不出这个图。所以从任意一个点出发，必定构成一个环回到这个点。

这个环长度显然最大是 $hw$，若取到 $hw$ 说明正好构成哈密顿路径，小于 $hw$ 则说明不合法。

所以问题转化为统计有多少个路径选择存在一个长度小于 $hw$ 的环。

Observation #4

从一个点向下或向右不重复地走，经过的 $g$ 个点，一定恰好在 $g$ 个不相同的对角线上。

画几个图感性理解一下。

略证：

假设从第一个点 $(x,y)$ 开始走 $k$ 步（$k\leq g$）到达了 $(x’,y’)$，且第一次出现 $(x’,y’)$ 与 $(x,y)$ 在同一对角线的情况，则有：

$x+d_x+k’\equiv x’(\bmod h),y+d_y-k’\equiv x’(\bmod w)$

其中 $d_x+d_y=k$。

因为是第一次出现，容易知道 $d_x+k’=d_y-k’=\operatorname{lcm}(h,w)=\frac{hw}{g}$，两式相加进而有 $d_x+d_y=\frac{2hw}{g}=k\leq g$。

得 $2hw\leq g^2$，显然不成立，得证。

最终章

上面的结论启示我们不要去关心这 $g$ 个对角线具体是怎么走的，转而去考虑这些总共产生的影响。

不妨假设在这 $g$ 条对角线中有 $k$ 条往右走，剩下 $g-k$ 条往下走，则每走 $x$ 轮最终产生的移动影响是 $(x(g-k),xk)$。

因为总是要回到原点，所以有 $h|x(g-k)$ 和 $w|xk$。

根据上面的 Observation #4，我们知道从一个点走到这个点一定经历了整数轮对角线。如果 $x<\frac{hw}{g}$，那么说明存在长度小于 $hw$ 的环。

现在考虑枚举 $k$，计算哪些 $k$ 不符合哈密顿路径。

不难发现只要找到最小的 $x$ 满足 $h|x(g-k)$ 且 $w|xk$ 再判断这个 $x$ 是否小于 $\frac{hw}{g}$ 即可。

若 $w|xk$，两边同除 $\gcd(w,k)$ 则有 $\frac{w}{\gcd(w,k)}|x\frac{k}{\gcd(w,k)}$。此时 $\frac{w}{\gcd(w,k)}$ 与 $\frac{k}{\gcd(w,k)}$ 互质，则有 $\frac{w}{\gcd(w,k)}|x$，同理有 $\frac{h}{\gcd(h,g-k)}|x$。

所以最小的 $x=\operatorname{lcm}(\frac{w}{\gcd(w,k)},\frac{h}{\gcd(h,g-k)})$。