FPS24 H - ジャンプ

考え方

方針が $2$ つある。
どちらでも手計算で答えが出る。

方針 $1$

$x$ 軸方向に移動しない操作をひとまとめにする。
$y$ 軸方向に正の整数 $k$ だけ移動するとき、間の距離 $1$ ごとに止まるか止まらないかの選択がある。
よって、その移動の仕方は $2^{k-1}$ 通りである。
また、移動しないのは $1$ 通りなので、母関数は以下のようになる。
$$
A(y) = 1+y+2y^2+4y^3+8y^4+\dots = 1+\dfrac{y}{1-2y} = \dfrac{1-y}{1-2y}
$$

また、$x$ 軸方向への移動がある操作の母関数は、以下である。
$$
B(y) = 1+y+y^2+y^3+y^4+\dots = \dfrac{1}{1-y}
$$

よって、$x$ 軸方向に $N$ 回移動する遷移の母関数は、以下のようになる。
$$
\{A(y)\}^{N+1}\{B(y)\}^N = \dfrac{1-y}{(1-2y)^{N+1}}
$$

これの $y^M$ の係数を考えればいいが、分子が $1$ 次式なので、手計算で対応できる。
答えは ${}_{M+N}\mathrm{C}_{N}2^M-{}_{M+N-1}\mathrm{C}_{N}2^{M-1}$ である。
計算量は、二項係数の下準備が支配的で、$O(M+N)$ になる。

方針 $2$

$2$ 変数の形式的冪級数を考える。
$x$ 軸方向への移動に対応する文字を $x$、$y$ 軸方向への移動に対応する文字を $y$ とする。
1回の操作の母関数は、以下である。
$$
A(x) = (y+y^2+y^3+\dots)+x(1+y+y^2+\dots) = \dfrac{x+y}{1-y}
$$

つまり、任意回の操作での母関数は、以下である。
$$
1+A(x)+\{A(x)\}^2+\{A(x)\}^3+\dots = \dfrac{1}{1-A(x)} = \dfrac{1-y}{1-x-2y}
$$

この式の $x^Ny^M$ の係数が答え。
まず、$y$ を定数と思って $x^N$ の係数を考えると、$\dfrac{1-y}{(1-2y)^{N+1}}$ になる。

入力例1での動作

入力を受け取る。

n: 2
m: 1

求める値は以下。
$$
{}_{3}\mathrm{C}_{2}2^1-{}_{2}\mathrm{C}_{2}2^0
=3\times 2-1
=5
$$

よって、答えは $5$ となる。

注意点

二項係数は $998244353$ で割った余りを求めながら計算する。
階乗を用いて二項係数を求める際の除算には逆元を用い、逆元や $2$ の累乗は繰り返し二乗法で求める。

別解

特になし。