abc240G Teleporting Takahashi

ziyistudy · 2024-04-18 18:27:28 · 题解

这是一个三维的问题，但我们将首先考虑一维网格上的简化版本，然后将其扩展到二维，以及原始的三维版本。

一维

考虑下面的问题：

开始时，他在一个无限一维网格上的 0 号方格中。当他位于 x 号方格时，他可以移动到 x-1 号方格或 x+1 号方格。在走了 N 步之后，有多少种方法可以到达 X 格？

如果是 N < |X|，那么经过 N 步不可能到达 X 格，因此答案是 0。
另外，移动奇数次后，得到的位置 x 总是奇数，而移动偶数次后，x 总是偶数，所以如果是 N \bmod 2 \neq X \bmod 2，答案也是 0。

我们再考虑其他情况。不妨设 X \geq 0（X < 0 是同样的），那么"在恰好下了 N 步之后，他在 X 格中"，当且仅当"在 N 步中，他在 x 坐标的正方向下了 (N+|X|)/2 步，在 x 坐标的负方向下了 (N-|X|)/2 步"。因此，所需的移动次数可以用二项式系数表示为 \binom{N}{(N+|X|)/2}。

因此，恰好经过 N 步到达 X 格的 f_1(N, X) 步数为：

通过预处理，可以在 \mathrm{O}(1) 的时间将给定的 N 和 X 计算出 f_1(N, X)。

二维

考虑下面的问题：

开始时，他在一个无限二维网格上的 (0, 0) 号方格中。当他位于 (x, y) 号方格时，他可以移动到 (x-1, y), (x+1, y), (x, y-1), (x, y+1) 号方格。经过 N 次移动后，有多少种方法可以到达 (X,Y) 号方格？

为了解决这个问题，我们在 xy 坐标上引入以下坐标变换：

ps：这一步类似于这个题目，我也写了题解。思路其实就是将棋盘旋转 45 度。

我们将把问题改写为 uv 坐标上的问题。同时，让 (U, V) := (X+Y, X-Y)。

那么"N 步之后到达 (X, Y) 格的方法数"等于"N 步之后到达 (u, v) = (U, V) 格的方法数"。

同样，在 uv 坐标系中，"当他在 (x, y) 位时，他可以移动到 (x-1, y), (x+1, y), (x, y-1), (x, y+1) 位"的对应关系是 "当他在 (u, v) 位时，他可以移动到 (u-1, v-1), (u-1, v+1), (u+1, v-1), (u+1, v+1) 位"。因此，每次移动时，"是否增加或减少 u"和"是否增加或减少 v"都可以独立的确定。

因此，为了确定恰好经过 N 步到达 (u, v) = (U, V) 的方法，我们可以独立地选择以下两条路线：

• 沿着 u 轴经过 N 步到达 u = U 的路线（f_1(N, U) 个选择）。
• 沿着 v 轴经过 N 步到达 v = V 的路线（f_1(N, V) 个选择）。

因此经过恰好 N 步到达 (X, Y) 号方格的 f_2(N, X, Y) 方法数可以表示为：

三维

最后我们来看看最初的三维问题。

我们将计算方案数：沿着 z 轴走 k 次最后到达 (X, Y, Z)。该方案数由以下三个因素决定：

• 有 \binom{N}{k} 种方法可以选择 N 步中的 k 步是沿着 z 轴的方向走；
• 选择沿 z 轴走 k 步，使他在沿 z 轴走 k 步之后到达 z = Z，因此有 f_1(k, Z) 种方法；
• 在 x 轴以外的方向上选择其他 (N-k) 次移动，使其在二维 xy 网格上经过 (N-k) 次移动后到达 (x, y) = (X, Y)，因此有 f_2(N-k, X, Y) 种方法。

因此，沿着 z 轴走 k 次最后到达 (X, Y, Z) 的方案数：

通过求出 k = 0, 1, \ldots, N 上的和，这个问题 f_3(N, X, Y, Z) 的答案为：

通过预处理，计算所需的二项式都只需 \mathrm{O}(1) 的时间，因此计算 f_3(N, X, Y, Z) 总共只需 \mathrm{O}(N) 时间。

因此，该题总时间复杂度为：\mathrm{O}(N)。

code