Teleporting Takahashi

题目描述

Takahashi 位于无限三维网格的方格 $(0, 0, 0)$。 他可以在方格之间瞬移。 从方格 $(x, y, z)$，他可以在一次瞬移中移动到 $(x+1, y, z)$、$(x-1, y, z)$、$(x, y+1, z)$、$(x, y-1, z)$、$(x, y, z+1)$ 或 $(x, y, z-1)$。（注意他不能停留在方格 $(x, y, z)$。） 求恰好经过 $N$ 次瞬移后到达方格 $(X, Y, Z)$ 的路径数。 换句话说，求满足以下三条条件的 $N+1$ 个整数三元组序列 $\big( (x_0, y_0, z_0), (x_1, y_1, z_1), (x_2, y_2, z_2), \ldots, (x_N, y_N, z_N)\big)$ 的数量。

$(x_0, y_0, z_0) = (0, 0, 0)$。 $(x_N, y_N, z_N) = (X, Y, Z)$。 对每个 $i = 1, 2, \ldots, N$，有 $|x_i-x_{i-1}| + |y_i-y_{i-1}| + |z_i-z_{i-1}| = 1$。

由于结果可能非常大，请对 $998244353$ 取模后输出。

输入格式

输入从标准输入按照以下格式给出： $N$ $X$ $Y$ $Z$

输出格式

输出对 $998244353$ 取模的路径数。

3 2 0 -1

3

1 0 0 0

0

314 15 92 65

106580952

提示

$1 \leq N \leq 10^7$ $-10^7 \leq X, Y, Z \leq 10^7$ $N$, $X$, $Y$, 和 $Z$ 都是整数。恰有三条路径在恰好 $3$ 次瞬移后到达方格 $(2, 0, -1)$：

$(0, 0, 0) \rightarrow (1, 0, 0) \rightarrow (2, 0, 0) \rightarrow(2, 0, -1)$ $(0, 0, 0) \rightarrow (1, 0, 0) \rightarrow (1, 0, -1) \rightarrow(2, 0, -1)$ $(0, 0, 0) \rightarrow (0, 0, -1) \rightarrow (1, 0, -1) \rightarrow(2, 0, -1)$
注意必须恰好进行 $N$ 次瞬移，并且不允许停留在相同位置。
请务必对 $998244353$ 取模后输出。

标签: AtCoder|abc240G

来源

AtCoder|abc240G