部分点 2 の解法 をもとに計算量を改善します。

上記の DP において、\(i\) 個目の区間を採用する場合の全体への寄与を考えます。以降 0-indexed です。

\(i\) 個目の区間を採用する場合の数は (\(i\) 個を採用する条件のもと、前 \(i\) 個の区間を並べる場合の数) \(\times (2i + 3) (2i + 5) \ldots (2N - 1)\) となります。(左端をどこに挿入するかを考える)

なので、すべての \(i\) について前者が分かれば良いです。

前者は、上記の部分点解法における dp[i + 1][i * 2 + 2] の場合の数に相当します。

これを \(f_i\) と書くことにします。 \(f_i\) の寄与の元は、DP の遷移を考えると、\(i\) 以前に選んだ最後の区間のインデックスごとに分解することができます。

例えば、i = 4 のとき、 \(f_4 = 1 \times f_3 + (6) \times 2f_2 + (4 \times 5) \times 3 f_1 + (2\times 3\times 4) \times 4f_0\)

と、\(f\) と、区間積と最後の遷移の係数の掛け算の形に分解できることが分かります。

これは

\[f_n = \displaystyle\sum_{i=0}^{n-1} \dfrac{(n + i)!}{(2i + 1)!} (n-i) f_i\]

と書くことができます。これは分割統治で計算することができます。 計算量は \(O(N \log ^2 N)\) です。

\(g_i = f_i - dp[i + 1][i * 2 + 1] = f_i - 2i f_{i-1}\)

という値を導入すると、

\[g_i = -\displaystyle\sum_{k=0}^{i-1} (i + k)! \dfrac{g_k}{(2k)!}\]

と変形することができます。(これを直接導くこともできます。)

こちらの方が分割統治が計算しやすいかもしれません。

原案 : nok0

解答 : noimi