ACL Begginer Contest F - Heights and Pairs 解説

解説する問題を以下に引用しておきます ( 引用元 : Heights and Pairs )

問題文

$2N$ 人の人 ( $1$ 番から $2N$ 番まで ) がいます。人 $i$ の身長は $h_i$ です。以下の条件を満たすように、$N$ 個の人のペアを作る方法は何通りありますか？答えを modulo $998,244,353$ で求めてください。

どの人もちょうど一つのペアに含まれる。

どのペアも、そのペアに属する二人の人の身長が異なる。

ある $p$ と $q$ に対し、人 $p$ と人 $q$ がペアになったかどうかが異なる場合、異なる方法であるとみなします。

制約

$1 \leq N \leq 50,000$

$1 \leq h_i \leq 100,000$

入力は全て整数である。

まず，そのまま数えるのは難しそうなので包除原理の適用を考えます．$P_i$ を「 $2N$ 人の中から身長が同じであるペアを $i$ 組選ぶ場合の数」，$Q_i$ を「$2i$ 人を $i$ 個のペアに分ける場合の数」と定義すると，求める値は次のようになります．

\[ \sum _ {i=0}^ {N} (-1) ^ i \cdot P _ i \cdot Q _ {N-i} \]

一般に $\displaystyle Q _ M=\frac{{} _ {2M}C _ {2} \cdot {} _ {2M-2}C _ {2} \cdot\ \cdots\ \cdot {} _ {2}C _ {2}}{M!}=\frac{(2M)!}{2 ^ M \cdot M! }$ なので，あとは $P_i$ が高速に求まればこの問題は解けます．

身長の大小に意味は無く，等しいかのみが重要なので，身長に対するヒストグラムを考えます．つまり，身長 $j$ の人が何人いるかをカウントしておきます．これを $S_j$ とします．

例えば ${S_j}=[3, 1, 2, 4, 1, 0, 5]$ として，$i=4$ 組の身長が同じペアを選ぶとすると，以下のような選び方が考えられます．

図 1 : ペアの数が $[1,0,0,1,0,0,2]$ であるような選び方の例

図 2 : ペアの数が $[1,0,1,0,0,0,2]$ であるような選び方の例

ここで，身長が $j$ の人たちから $k$ 個のペアを作る場合の数を $A(j, k)$ とすると，$P_i$ は以下のように表せることが分かります．ただし，式中の $a _ j$ は身長が $j$ の人から選ぶペアの数で，図 1 における $[1,0,0,1,0,0,2]$ や図 2 における $[1,0,1,0,0,0,2]$ を指します．

\[ P _ i = \sum _ {\sum a _ j = i}\prod _ {j} A(j, a _ j) \]

$A(j, k)$ は $S_j$ 人の中から $2k$ 人を選んで $k$ 組のペアを作る場合の数なので $\displaystyle A(j,k)={} _ {S _ j}C _ {2k}\cdot Q _ k=\frac{S _ j!}{2 ^ k\cdot(S _ j-2k)!\cdot k!}$ です．

以上より，各 $j$ に対して形式的冪級数 $f_j$ を

\[ f _ j=\sum _ {k=0} ^ {\lfloor S _ j/2\rfloor}A(j, k)\cdot x ^ k=\sum _ {k=0} ^ {\lfloor S _ j/2\rfloor}\frac{S _ j!}{2 ^ k\cdot(S _ j-2k)!\cdot k!}\cdot x ^ k \]

で定義すると， $\displaystyle \prod _ {j} f _ j=\sum _ {i=0} ^ {N}P _ i\cdot x ^ i$ となるので，左辺の積が高速に求まればよいです．

$\displaystyle \sum _ {j} S _ j=2N$ なので，$f_j$ の次数の和は高々 $N$ です．従って，FFT とマージテクを用いれば左辺は $O(N(\log N) ^ 2)$ で求めることが出来ます．

あとは，求めた $P _ i$ と $Q _ i$ を用いて冒頭に示した和を計算すれば良いです．階乗の逆元などを適切に前処理しておくことで，全体 $O(N(\log N) ^ 2)$ でこの問題を解くことができます．