kaage https://blog.hatena.ne.jp/kaage/ kaage精進録 https://kaage.hatenablog.com/ 問題リンク 数え上げ，苦手 解説 数をグループにして考える．$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^2… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkaage.hatenablog.com%2Fentry%2F2021%2F03%2F01%2F020050" title="ACL Beginner Contest F - Height and Pairs 解説 - kaage精進録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/154818125/1592546778599961 Hatena Blog https://hatena.blog 2021-03-01 02:00:50 rich https://kaage.hatenablog.com/entry/2021/03/01/020050 1.0 100%