ACL Beginner Contest F - Height and Pairs 解説
数え上げ，苦手
解説
数をグループにして考える．$h$ に含まれる $i$ の数を $n_i$ としておく．
$n_i$ 個の数があるグループの中に重複を少なくとも $k$ ペア作る方法の数は $\binom{n_i}{2k}(2k-1)!!$ 通りある． これを多項式の係数にして畳み込みすると，全体について重複を少なくとも $k$ ペア作る方法の数が求まる． これが求まったら，残りの組み方は $(2N-2K-1)!!$ 通りあるので，これをかけて包除すると解ける．
畳み込みは，FFTを平衡二分木を作る要領でやると $O(N\log^2N)$ なので，全体でも $O(N\log^2N)$ で解けた．
感想
畳み込みに帰着，なるほどなあという感じ
