挿入 DP による数え上げ

順列に関する数え上げの問題では，しばしば 挿入DP という考え方が有効です．挿入DP では，順列を要素の昇順または降順に見ていって，要素を列のどの位置に挿入するかによって求めたい値がどのように変化するかを考えます．

今回は，要素を降順に見るとうまく行きます．\(\mathrm{dp}(i,k)\;(i=0,\dots,N-1,\,k=-i,\dots,i)\) を，\((N-i,N-i+1,\dots,N)\) の順列であって，\(L-R=k\) となるものの個数とします．\(\mathrm{dp}(0,0) = 1\) です．いま，\(\mathrm{dp}(i,k)\) がすべての \(k\) に対して求まっているとし，\(\mathrm{dp}(i+1,k)\) を求める方法を考えます．

\((N-i,N-i+1,\dots,N)\) の順列に \(N-i-1\) を挿入する方法は \(i+2\) 通りあります．\(N-i-1\) を挿入する位置によって，\(L,R\) がどう変化するかを考えましょう．

• 左端に挿入する場合：\(N-i-1\) が新たに左側から見えるようになります．また，\(N-i-1\) はいまある列の最小の要素なので，それがもともと左側から見えていた数を遮ることはありません．また，\(N-i-1\) は右側からは見えません．よって，\(L\) が \(1\) 増え，\(R\) は変わらないので， \(L-R\) が \(1\) 増えます．
• 右端に挿入する場合：左端に挿入する場合と同様に考えると，\(L-R\) が \(1\) 減ることが分かります．
• それ以外の場所（\(i\) 箇所ある）に挿入する場合：\(N-i-1\) は左からも右からも見えません．よって，\(L-R\) は変わりません．

以上の考察より，次のようなDPの遷移で答えを求めることができます．

\[ \mathrm{dp}(i+1,k) = \mathrm{dp}(i,k-1) + \mathrm{dp}(i,k) \times i + \mathrm{dp}(i,k+1) \]

以上のDPをそのまま実装すると，\(O(N^2)\) 時間の解法が得られます．

形式的冪級数による高速化

多項式 \(f_i(x)\) を， \(x^k\) の係数が \(\mathrm{dp}(i,k)\) であるようなものとします．\(f_0(x) = 1\) です．DPの遷移は，次のように多項式の積に対応します．

\[ f_{i+1}(x) = (x^{-1} + i + x) f_i(x) \]

求める答えは，\(f_{N-1}(x)\) の \(x^K\) の係数（これを \([x^K] f_{N-1}(x)\) と表す）であり，これは

\[ [x^K] f_{N-1}(x) = [x^K] \prod_{i=0}^{N-2}(x^{-1}+i+x)f_0(x) = [x^{K+N-1}] \prod_{i=0}^{N-2}(1+ix+x^2) \]

となります．よって，最右辺の \(N-1\) 個の \(2\) 次多項式の積を高速に計算できれば，この問題を解くことができます．

\(2\) つの \(N\) 次以下の多項式は \(O(N \log N)\) 時間で畳み込むことができます．これを用いて \(N-1\) 個の \(2\) 次多項式を前から順番に畳み込んでいくと，全体で \(O(N^2 \log N)\) 時間かかってしまいます．実は，次数の総和が \(N\) であるような多項式の列 \(p_1,\dots,p_M\) の積は \(O(N (\log N)^2)\) 時間で計算することができます．2 つの方法を紹介します．

1 つは マージテク と呼ばれるテクニックで，次数が最も低い \(2\) つの多項式を選んでそれらを畳み込むことを繰り返すという方法です．

もう 1 つは 分割統治法 で，多項式の列を \(2\) つに分割して，それぞれの列の積を再帰的に計算し，最後にそれらの積を計算して全体の積を得るという方法です．すなわち，\((p_1,\dots,p_{\lfloor M/2 \rfloor})\) の積 \(q_1\) と \((p_{\lfloor M/2 \rfloor+1},\dots,p_M)\) の積 \(q_2\) をそれぞれ計算し（それぞれの積を計算するときも，再帰的に分割することを繰り返す），最後に積 \(q_1q_2\) を計算するという方法です．