適当に並び替えることで, \(M\)は昇順であるとします。

まず選出された\(K\)人をアイドル\(i_1, i_2,\cdots,i_K(1\leq i_1<i_2<\cdots<i_K\leq N)\)とした場合に, 衣装が一致する確率を考えます。\(K\)人の衣装の選び方は, 全体で\(\prod_{j=1}^K M_{i_j}\)通りあり, その内衣装が一致するのは\(M_{i_1}\)通りなので, その確率は\(\prod_{j=2}^K M_{i_j}^{-1}\)となります。

よって選出されるアイドルを全通り考えると, 求める確率は

\[ \frac{\sum_{1\leq i_1<\cdots<i_K\leq N}\prod_{j=2}^K M_{i_j}^{-1}}{\binom NK} \]

となります。ここで\(f_i = 1 + M_i^{-1}x\)として, 多項式\(f\)の\(k\)次の係数を\([x^k]f\)と書くこととすると, 求める確率は

\[ \frac{\sum_{1\leq i_1\leq N}[x^{K-1}]\prod_{j=i_1+1}^N f_{j}}{\binom NK}= \frac1{\binom NK}\sum_{1\leq i_1\leq N}[x^{K-1}]\prod_{j=i_1+1}^Nf_{j} \]

となります。\(d\)次多項式に1次多項式をかける操作は\(O(d)\)でできることに気をつけて, これは素朴に計算しても\(O(N^2)\)乃至\(O(NK)\)で計算可能で, 部分点を獲得できます。

適当に\(N\)や添字などをずらして, 簡単に\(\displaystyle\sum_{0\leq i < N}\prod_{i\leq j<N}f_j\)を求めることを考えます。ここで\(l<m<r\)に対して

\[ \prod_{l\leq j < r}f_j =\left( \prod_{l\leq j < m}f_j \right)\left(\prod_{m\leq j < r}f_j\right)\\ \sum_{l\leq i < r}\prod_{i\leq j<r}f_j = \left( \sum_{l\leq i < m}\prod_{i\leq j<m}f_j\right)\left(\prod_{m\leq j < r}f_j\right)+ \sum_{m\leq i < r}\prod_{i\leq j<r}f_j \]

となっていることに気をつけると, 分割統治とFFT(FFTのマージテクとかとも呼ばれるものの一種)を用いて計算することで, \(O(N\log^2N)\)で計算可能となり, 満点が獲得できます。

また多項式の計算を\(K-1\)次までで打ち切ることで\(O(N\log N\log K)\)となります。

実装上は抽象化セグメント木に載せると簡単に書けます。