まず、この手の問題に対する典型的なアプローチとして鏡像法(反射原理とも)を適用することを考えたいですが、この問題に鏡像法をそのまま適用することは難しそうです。そこで一工夫します。

毎回の操作において、\(8\) 近傍への移動に加えて「移動しない」という選択も選べることにします。

• 元の問題の \(T=t\) の時の答えを \(f(t)\)
• 「移動しない」を追加した操作を \(t\) 回行った時に \((A,B)\) から \((C,D)\) へ移動する方法の個数を \(g(t)\)

とすると

\[g(T) = \sum_{t=0}^T \binom{T}{t} f(t) \iff f(T) = \sum_{t=0}^T (-1)^{T-t} \binom{T}{t} g(t)\]

が成り立つため、\(g(0), g(1), \dots, g(T)\) を計算できれば求めたい答えである \(f(T)\) が計算できることがわかります。
そして、「移動しない」を追加した操作を観察すると、これは行方向に \(h \in \lbrace -1,0,1 \rbrace\) 移動した後に列方向に \(w \in \lbrace -1,0,1 \rbrace\) 移動する、という風に読み替えられるので、2 軸を独立に考えてもよくなります。

以上の考察により、結局次の問題が解ければよいことになります。

言い換え後の問題

次の問題を \(t=0,1,\dots,T\) について解け。

• \(1 \times N\) の将棋盤の左から \(S\) 列目に駒がある。あなたは「左に駒を動かす」「右に駒を動かす」「駒を動かさない」という \(3\) 択の操作を \(t\) 回繰り返す。ただし盤の外へ駒は動かせない。\(t\) 回の操作を終えた後に左から \(G\) 列目に駒がある方法の個数は？

言い換え後の問題は鏡像法および特殊な分割統治 FFT を用いれば解けます。鏡像法の例題は ABC309Ex、特殊な分割統治 FFT の例題は ABC281H および ABC345G があります。これらの問題の解説でアルゴリズムが詳説されているのでそちらも参考にしてください。

\(1, 2, \dots, N-1, N, M_1, N', N-1', \dots, 2', 1', M_2\) という \(2N+2\) 頂点がこの順に並んだサイクルグラフを考えます。(\(M_\ast\) は鏡(mirror)を意味します)
求めたい答えは、\(1\) 回の操作において「隣接する頂点に移動」or「動かない」という \(3\) 択の操作が選べる時に、頂点 \(S\) から頂点 \(G\) へ \(t\) 回の操作で移動する方法の個数です。ここで「頂点 \(S\) から \(M_\ast\) を経由して \(G\) へ移動する方法の個数」は「頂点 \(S\) から \(M_\ast\) を経由して \(G'\) に移動する方法の個数」と等しいことが証明できるため、結局

• 「頂点 \(S\) から頂点 \(G\) へ \(t\) 回の操作で移動する方法の個数」から
• 「頂点 \(S\) から頂点 \(G'\) へ \(t\) 回の操作で移動する方法の個数」

を引けばよいことがわかります。

母関数を用いて上記の問題を言い換えると、適切な定数 \(M\) および \(t=0,1,\dots,T\) に対して

\[[x^0] x^M (x+1+x^{-1})^t \bmod {x^{2N+2} - 1}\]

が計算できればよいということになります。(上式の \(\text{mod } {x^{2N+2}-1}\) は全ての係数における \(x\) の指数 \(e\) を \(2N+2\) で剰余を取って \(0 \leq e \lt 2N+2\) の範囲に収める演算子という意図で記述しています。)

そしてこの問題は特殊な分割統治 FFT で計算できます。簡単に説明します。今、\(t=L,L+1,\dots,R-1\) の範囲の答えに興味があるとします。そして \(x^M (x+1+x^{-1})^L\) の情報を持っているとします。この時、興味がある答えを求めるときに \(x^M (x+1+x^{-1})^L\) に対して高々 \((x+1+x^{-1})\) を \(R-L-1\) 回しか掛けないことから、\(x\) の指数が \(x^0\) から \(R-L\) 以上離れている係数の情報は切り捨ててしまっても問題ないことがわかります。ここから次の Python 風擬似コードで書かれたアルゴリズムが従います。

ans = [0]*(T+1)

# ans[L:R] を計算する関数 (L, R は半開区間)
def f(L, R, prod):
  prod を x^{-(R-L-1)} から x^{R-L-1} の範囲に shrink する
  if L + 1 == R:
    ans[L] = prod[0]
    return
  M = (L + R) // 2
  f(L, M, prod)
  f(M, R, prod*(x+1+x^{-1})^{M-L})

f(0, T+1, x^M)

上記のアルゴリズムは (shirnk の部分が計算量に効いて) \(\mathrm{O}(T \log^2 T)\) で動作します。ただ (x+1+x^{-1})^{M-L} の部分の計算がやっかいなので、これも f(L,R,prod) の計算のついでに計算することにしましょう。すなわち、f(L,R,prod) の返り値を (x+1+x^{-1})^{R-L} にしてしまいましょう。これは簡単に追加できます。

ans = [0]*(T+1)

# ans[L:R] を計算して (x+1+x^{-1})^{R-L} を返す関数
def f(L, R, prod):
  prod を x^{-(R-L-1)} から x^{R-L-1} の範囲に shrink する
  if L + 1 == R:
    ans[L] = prod[0]
    return x+1+x^{-1}
  M = (L + R) // 2
  resL = f(L, M, prod)
  resR = f(M, R, prod*resL)
  return resL*resR

f(0, T+1, x^M)

これで完成です。上記のアルゴリズムは \(\mathrm{O}(T \log^2 T)\) で計算できて、要求されるライブラリも畳み込みのみです。(shrink において \(\text{mod }x^{2N+2}-1\) を随時適切に取る必要がある点に注意してください。)

以上よりこの問題を \(\mathrm{O}(T \log^2 T)\) 程度で計算することができて、これは十分高速です。なお、解説は省略しましたが \(\tilde{\mathrm{O}}((H+W+T)^{1.5})\) 程度の計算量の解法も存在して、定数倍が良好であればこれも通ると思います。(これは余談ですが、制約がだいぶ大きかったのは \(\mathrm{O}((H+W)T)\) 解法が非常に高速に動作していてこれを落とすためです。)