ペアの作り方

\(2p\) 個のものを \(2\) 個ずつの \(p\) 組のペアに分ける場合の数は二重階乗を用いて \((2p-1)!!\) となります。

高さごとに分類

\(h_i = x\) である \(i\) の個数を \(c_x\) とします。

\(x\) 同士でペアを構築してみます。

\(x\) 同士のペアになっている個数が\(p = 0, 1, \ldots, \lfloor c_x / 2 \rfloor\) 個以上である場合の数は

\[ \binom{c_x}{2p} (2p-1)!! \]

となります。

畳み込み

\[dp_{x, i} = \binom{c_x}{2p} (2p-1)!!\]

と定義します

これをすべての \(x\) について畳み込むと

\[A_i = \{i個の同じ数のペアができている場合の数\}\]

が求められます。

畳み込むときは\(c_x\) が小さい順に処理していくといいらしいです？。

残りの処理

まだ、同じ数同士でしかペアを作っていないので、

\[B_i = \{N組のペアができていて、すくなくともi個以上の同じ数のペアができている場合の数\}\]

を求めます。

\(A\) でペアになっていない残りをペアにすれば良いので、

\[B_i = A_i \times (2(N - i) - 1)!!\]

になります。

「すくなくともi個以上」としているのは、残ったペアでも同じ数になってしまう場合があるからです。

答えである同じ数のペアがない場合の数は、包除原理より

\[ \sum_{i=0}^{N} (-1)^iB_i \]

で求めることができます。

参考: 二重階乗(Wikipedia)
提出例(C#): https://atcoder.jp/contests/abl/submissions/31457224