公式解説の言い換え後の問題を解きます。

条件を満たす文字列 \(S\) を A, B からなる文字列 \(S^{\prime}\) に Xを挿入することで作ることを考えると、次の問題を高速に解ければ良いことが分かります。

xy平面上でx軸正かy軸正の方向に+1進むことを繰り返して \((0, 0)\) から \((a, b)\) に 向かうことを考える。 ただし、 \(p < q\) なる \((p, q)\) を通ってはいけない。

この時、「曲がる回数」、つまり進む方向を変える回数が \(K\) 回あるような経路は何通りあるか。

これは \(K\) が奇数の場合は、以下の条件を満たす狭義単調増加な正整数列 \(A\) , \(B\) を数える問題に言い換えられます:

\(A\) , \(B\) の長さは \(\frac{K+1}{2}\) であり、 \(1 \leq i \leq \frac{K+1}{2}\) なる \(i\) に対し \(A_i \geq B_i\) が成立し、 \(A\) の末尾の要素は \(a\) 、 \(B\) の末尾の要素は \(b\) である

すると、この問題はグリッド上の2本の非交差経路を数え上げる問題に言い換えられるため、LGV公式を用いると \(\mathrm{O}(1)\) で計算することができます。

\(K\) が偶数の場合も、上記の問題を \((a, b+1)\) に \((K+1)\) 回曲がって向かう場合の数から \((a, b)\) に \((K+1)\) 回曲がって向かう場合の数を引けば求めることができます。

( \(a = b\) の場合は考える必要がありません。)

以上より、この問題が \(\mathrm{O}(N)\) で解けました。