公式解説と同様に、\(i=1,2,⋯,2N\) に対して、\(i\) を区間の右端として使うか左端として使うかを順に決めていくことにします。また、右端として使うと決めた場合には、対応する左端をどれにするかも同時に定めることとします。

\[\mathrm{dp}_{i,j} = i\ \text{まで決めて}, 対応する右端が決まっていない左端が \ j\ \text{個である場合の数}\]

と定義すると、\(\mathrm{dp}_{i+1,j} =\mathrm{dp}_{i,j-1} +(j+1)\mathrm{dp}_{i,j+1}\) というように遷移ができます (問題の条件を満たすため、\(j>K\) のとき \(dp_{i,j}=0\) とします)。

ここで、形式的冪級数 \(f_j\) を、\(\displaystyle f_j = \sum_{i}\mathrm{dp}_{i,j}x^i \) と定義します。すると、先ほどの遷移の式から

\[f_j = xf_{j-1}+(j+1)xf_{j+1}\ \ (1 \leq j \leq K)\]

すなわち

\[f_{j+1} = \frac{f_{j}-xf_{j-1}}{(j+1)x}\ \ \ \ \ \ \ \ (1)\]

が導かれます (これは \(f\) に関する三項間漸化式です)。

また、

\[f_0 = 1+xf_1\]

より

\[f_1 = \frac{f_0-1}{x}\ \ \ \ \ \ \ \ (2)\]

であるため、式 \((1),(2)\) を繰り返し用いることで、任意の \(j\) に対して、\(f_j = P_jf_0+Q_j\) となる多項式 \(P_j,Q_j\) を求めることができます。しかし、\(f_0\) は分かりません (そもそも、\([x^{2N}]f_0\) を求めることが本問題の目的です)。ここで、境界条件として \(f_{K+1}=0\) が存在していることを思い出します。すると、

\[f_0 =-\frac{Q_{K+1}}{P_{K+1}}\ \ \ \ \ \ \ \ (3)\]

と表せることが分かるため、本問題は \(P_{K+1},Q_{K+1}\) を高速に求める問題に帰着できます。以下、帰着後の問題を解きます。

式の簡略化のため、式 \((1)\) の両辺に \((j+1)!x^{j+1}\) をかけると、

\[(j+1)!x^{j+1}f_{j+1} = j!x^jf_{j}-j^!x^{j+1}f_{j-1}\]

となり、\(g_j=j!x^jf_j\) と定義すれば、

\[g_{j+1}= g_j-jx^2g_{j-1}\]

と表せます。\(P_j,Q_j\) をそれぞれ \(j!x^jP_j,\ j!x^jQ_j\) として改めて置き直せば (この置き換えは式 \((3)\) に影響しません)、

\[P_{j+1}=P_j-jx^2P_{j-1}\]

\[Q_{j+1}=Q_j-jx^2Q_{j-1}\]

となり、

\[ \begin{pmatrix} P_{K+1} \\ P_{K} \\ \end{pmatrix} = \Biggl(\prod_{i=1}^{K} \begin{pmatrix} 1 & -ix^2 \\ 1 & 0 \\ \end{pmatrix}\Biggr) \begin{pmatrix} P_1 \\ P_0 \\ \end{pmatrix} \]

\[ \begin{pmatrix} Q_{K+1} \\ Q_{K} \\ \end{pmatrix} = \Biggl(\prod_{i=1}^{K} \begin{pmatrix} 1 & -ix^2 \\ 1 & 0 \\ \end{pmatrix}\Biggr) \begin{pmatrix} Q_1 \\ Q_0 \\ \end{pmatrix} \]

と表せます (総積部分は \(i\) が大きい順に左から並べるものとします)。

明らかに \(P_0=1,Q_0=0\) であり、式 \((2)\) より \(P_1=1,Q_1=-1\) ですから、あとは行列積の部分が求まれば良いですが、これは分割統治 FFT によって \(O(Klog^2K)\) で求まります。

よって、式 \((3)\) の計算の部分を含めて、\(O(NlogN+Klog^2K)\) で本問題を解くことができました。

おまけ：公式解説の最後に載っている OEIS の数列は、本解法では \(P_j\) の係数列として現れます。