最終的に得られるグラフを強連結成分分解すると、各強連結成分に含まれる頂点の番号は区間となります。 ここで、頂点 \(i\) と \(i+1\) が異なる成分に属するような \(i\,(1\le i \le 2N-1)\) を切れ目と呼ぶことにします。 求めるべきものは、切れ目が存在しないように頂点をペア分けする方法の数です。

ここで、\(i\) が切れ目となるための条件は、番号が \(i+1\) 以上の頂点から番号が \(i\) 以下の頂点へ向かう辺が存在しないことです。言い換えると、番号が \(i\) 以下の黒い頂点が全て、番号が \(i\) 以下の白い頂点のいずれかとペアになっていることです。

\(i_1<i_2<\ldots<i_k\) が切れ目となるようにペア分けをする方法の個数を求めます。 ここで、\(i_1,i_2,\ldots,i_k\) 以外の \(i\) は切れ目であってもなくても構いません。 便宜上、\(i_0=0,i_{k+1}=2N\) ということにします。

番号が小さい順に黒い頂点を見ていき、どの白い頂点とペアを組むかを決めていきます。 番号が \(i_l+1\) 以上 \(i_{l+1}\) 以下の黒い頂点について、ペアを組む方法の総数を考えます。 番号が \(i\) 以下の黒い頂点の個数を \(B_i\)、白い頂点の個数を \(W_i\) とします。

まず、ペアとなる白い頂点の候補の個数は、\(i_{l+1}\) が切れ目である条件により、番号が \(i_{l+1}\) 以下である白い頂点の個数から、番号が \(i_l\) 以下の黒い頂点ですでに用いた白い頂点の個数を引いた、\(W_{i_{l+1}}-B_{i_l}\) です。これらを \(B_{i_{l+1}}-B_{i_l}\) 個の黒い頂点に割り当てるので、そのような割り当ての方法の数は \(\dfrac{(W_{i_{l+1}}-B_{i_l})!}{(W_{i_{l+1}}-B_{i_{l+1}})!}\) です。ただし、\(W_{i_{l+1}}<B_{i_{l+1}}\) や \(W_{i_{l+1}}<B_{i_l}\) のときはそのような割り当ての方法の数は \(0\) です。

よって、包除原理を用いると、次の漸化式における \(dp_{2N}\) の値が答えとなることが分かります。

• \(dp_0 = -1\)

• \(dp_i = \sum\limits_{j=0}^{i-1}(-1)dp_j\dfrac{(W_i-B_j)!}{(W_i-B_i)!}\)

ただし、\(W_i<B_i\) や \(W_i<B_j\) のとき、\(dp_j\) から \(dp_i\) への寄与は \(0\) です。

この動的計画法を、分割統治と FFT を用いて高速化します。

\(j=1,2,\ldots,m\) と \(i=m+1,m+2,\ldots,2m\) について、\(j\) から \(i\) への寄与をまとめて計算できればよいです。

• \(x_b=\sum\limits_{j\leq m, B_j=b}dp_j\)

• \(y_s=s!\)

• \(z_w=\sum\limits_{b+s=w}x_by_s\)

としたとき、\(j=1,2,\ldots,m\) の \(dp_i\) への寄与の総和は、\((-1)\dfrac{z_{W_i}}{(W_i-B_i)!}\) と表されます。\(B_j=b\) となる \(j\) が存在するような \(b\) の区間の大きさは高々 \(m\) です。同様に、\(W_i=w\) となる \(i\) が存在するような \(w\) の区間の大きさも高々 \(m\) なので、この畳み込みの計算量は \(O(m\log m)\) です。

よって、全体で \(O(N\log^2N)\) の計算量でこの問題を解くことができました。