公式解説で使用されている 鏡像法(反射原理 とも) と呼ばれるテクニックについて簡単に説明します。

次の問題を考えます。

地点 \(1\), 地点 \(2\), \(\dots\), 地点 \(M\) がある。あなたは地点 \(S\) にいる。
1 秒経つごとに今いる地点を \(x\) として地点 \(x+1\) か地点 \(x-1\) に移動できる。(地点 \(0\), 地点 \(M+1\) は存在しないので行けない)
\(N\) 秒後に地点 \(T\) にいるような経路は何通りあるか？(mod 998244353)

この問題は \(\mathrm{O}(M \log M \log N)\) で解けます。

頂点に \(鏡_1, 1, 2, \dots, M, 鏡_2, M', \dots, 2', 1'\) のラベルがこの順に貼られている \(2M+2\) 点の cycle graph を考えます。(図は \(M=5\) の場合)

求めたい答えは

• (始点 \(S\), 終点 \(T\) の \(鏡_1, 鏡_2\) を経由しない \(N+1\) 頂点の walk の個数)
  \(=\) (始点 \(S\), 終点 \(T\) の \(N+1\) 頂点の walk の個数)
  \(-\) (始点 \(S\), 終点 \(T\) の \(鏡_1, 鏡_2\) を経由する \(N+1\) 頂点の walk の個数)

です。(walk とは, 同じ頂点や同じ辺を何回も使ってよい経路のこと)
ここで、次の 2 つの集合の間に全単射が成り立つことが証明できます。

• (始点 \(S\), 終点 \(T\) の \(鏡_1, 鏡_2\) を経由する \(N+1\) 頂点の walk ) からなる集合
  
• (始点 \(S'\), 終点 \(T\) の \(N+1\) 頂点の walk ) からなる集合

(証明) 前者の集合から 1 つ walk を取り \(p\) とする。\(p\) が経由する頂点の列を \(S = v_0, v_1, \dots, v_N = T \) とする。
\(p\) にはじめて登場する \(鏡\) が \(v_i\) であるとする。このとき、 \(v_0, v_1, \dots, v_{i-1}\) はすべて鏡から見て \(S\) 側 (つまりダッシュのつかない) 頂点となる。このとき、\(p\) に対応する walk \(q\) を次の条件を満たすように一意に取る。

• 経由する頂点の列が \({v_0}', {v_1}', \dots, {v_{i-1}}', v_i, v_{i+1}, \dots, v_N\) である。(つまり、\(p\) の \(v_j\) \((j \lt i)\) の範囲にダッシュをつけた頂点の列となる。)

\(1, 2, \dots, M\) と \(1', 2', \dots, M'\) が鏡映しの関係にあること、および\({v_0}' = S', v_N = T\) であることから、 \(q\) は \(S'\) から \(T\) への walk として正当であることが確認できる。
また、逆操作をすると後者の集合に含まれるパス \(q\) から \(p\) を復元することも可能であるから、2 つの集合の要素の間で一対一対応を取ることができる。(証明終わり)

よって、求めたい答えは

• (始点 \(S\), 終点 \(T\) の \(N+1\) 頂点の walk の個数)
  \(-\) (始点 \(S'\), 終点 \(T\) の \(N+1\) 頂点の walk の個数)

で、DP で計算できる問題に帰着しました。これはナイーブな DP で \(\mathrm{O}(NM)\), 畳み込みで高速化して \(\mathrm{O}(M \log M \log N)\) で計算できます。
このテクニックを利用すると公式解説と同様の DP を導くことができます。

関連ブログ：noshi さんによるカタラン数の鏡像法による説明