本問題は三次元グリッドにおける問題ですが、まずは一次元の問題として簡単化したものを考え、次に二次元、そして本来の三次元の場合へと話を進めます。

[1] 一次元の問題

次の問題を考えます。

はじめ、無限に続く一次元グリッドのマス \(0\) にいる。マス \(x\) にいるとき \(1\) 回の移動でマス \(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\) 回のうち \((N+|X|)/2\) 回は \(x\) の正の（負の）方向に、残りの \((N-|X|)/2\) 回は \(x\) の負の（正の）方向に移動する」ことと同値です。 よって、求める移動経路の個数は、二項係数を用いて \(\binom{N}{(N+|X|)/2}\) と表せます。

以上から、ちょうど \(N\) 回の移動後にマス \(X\) にいる移動経路の個数 \(f_1(N, X)\) は、

\[ f_1(N, X) = \begin{cases} \displaystyle\binom{N}{(N+|X|)/2} &(N \geq |X| かつ N \bmod 2 = X \bmod 2の場合)\\ 0&(上記以外の場合) \end{cases} \]

です。

必要な階乗の値を前計算しておくと、与えられた \(N\) と \(X\) に対して \(f_1(N, X)\) を \(\mathrm{O}(1)\) 時間で計算できます。

[2] 二次元の問題

次の問題を考えます。

はじめ、無限に続く二次元グリッドのマス \((0, 0)\) にいる。マス \((x, y)\) にいるとき \(1\) 回の移動でマス \((x-1, y), (x+1, y), (x, y-1), (x, y+1)\) のいずれかに移動する。ちょうど \(N\) 回の移動後にマス \((X, Y)\) にいるような移動経路は何通りか？

これを解くために、\(xy\) 座標に対して

\[ \begin{cases} u = x+y\\ v = x-y\\ \end{cases} \]

という座標変換を導入し 、以下で \(uv\) 座標を使って問題を捉え直します。 また、\((U, V) := (X+Y, X-Y)\) とおきます。

このとき「ちょうど \(N\) 回の移動後にマス \((X, Y)\) にいるような移動経路は何通りか？」は「ちょうど \(N\) 回の移動後に \((u, v) = (U, V)\) であるような移動経路は何通りか？」と捉え直すことができます。

また、「マス \((x, y)\) にいるとき \(1\) 回 の移動でマス \((x-1, y), (x+1, y), (x, y-1), (x, y+1)\) のいずれかに移動する」ことは、 \(uv\) 座標系で見ると 「 \((u, v)\) にいるとき \(1\) 回の移動で \((u-1, v-1), (u-1, v+1), (u+1, v-1), (u+1, v+1)\) のいずれかに移動する」ことになります。 このことから、移動の際には「 \(u\) を \(1\) 増やすか \(1\) 減らすか」と「 \(v\) を \(1\) 増やすか \(1\) 減らすか」を独立に決められることがわかります。

したがって、ちょうど \(N\) 回の移動後に \((u, v) = (U, V)\) であるような移動経路を \(1\) つ選ぶには、

• \(u\) 軸方向に \(N\) 回移動後に \(u = U\) であるような移動経路（ \(f_1(N, U)\) 通り）と
• \(v\) 軸方向に \(N\) 回移動後に \(v = V\) であるような移動経路（ \(f_1(N, V)\) 通り）

を独立に選べばよく、ちょうど \(N\) 回の移動後にマス \((X, Y)\) にいる移動経路の個数 \(f_2(N, X, Y)\) は、

\[ f_2(N, X, Y) = f_1(N, U) f_1(N, V) = f_1(N, X+Y) f_1(N, X-Y) \]

と書けます。

[3] 三次元の問題

本来の三次元グリッドの問題を考えます。

ちょうど \(N\) 回の移動後にマス \((X, Y, Z)\) にいる移動経路のうち、\(z\) 軸方向に移動する回数が \(k\) 回のものの個数を考えます。 そのような移動経路を \(1\) つ選ぶとき、

• \(N\) 回の移動のうち、\(z\) 軸方向に移動する \(k\) 回を選ぶ方法が \(\binom{N}{k}\) 通りあります。
• \(z\) 軸方向への \(k\) 回の移動方法は、\(z\) 軸上で \(k\) 回移動のあとに \(z = Z\) であるように選ぶので、\(f_1(k, Z)\) 通りの選び方があります。
• \(z\) 軸方向以外への \(N-k\) 回の移動方法は、\(xy\) 二次元グリッド上で \(N-k\) 回移動したあとに \((x, y) = (X, Y)\) であるように選ぶので、\(f_2(N-k, X, Y)\) 通りの選び方があります。

よって、ちょうど \(N\) 回の移動後にマス \((X, Y, Z)\) にいる移動経路のうち、\(z\) 軸方向に移動する回数が \(k\) 回のものの個数は

\[ \binom{N}{k} f_1(k, Z) f_2(N-k, X, Y) \]

です。\(k = 0, 1, \ldots, N\) にわたるこれの和をとることで、 本問題の答え \(f_3(N, X, Y, Z)\) が

\[ f_3(N, X, Y, Z) = \sum_{k = 0}^N \binom{N}{k} f_1(k, Z) f_2(N-k, X, Y) = \sum_{k = 0}^N \binom{N}{k} f_1(k, Z) f_1(N-k, X+Y) f_1(N-k, X-Y) \]

と得られます。適切な前計算によって必要な二項係数を \(\mathrm{O}(1)\) 時間で求められるように準備しておくことで、\(f_3(N, X, Y, Z)\) は \(\mathrm{O}(N)\) 時間で計算できます。

以上で、本問題を \(\mathrm{O}(N)\) 時間で解くことができます。