問題
解説
問題では「色を塗る」→「ボールを選ぶ」の順番ですがこれを入れ替えます. すなわち, 以下の問題を解きます.
$N$ 個のボールのうちいくつかを選びます. 選んだボールに登場する色の数がちょうど $K$になるような塗り方の通り数を選び方全てに対して足し合わせてください.
選ぶ個数 $n$ を固定します. このとき, ボールの選び方は $\displaystyle\binom{N}{n}$ 通り, 色の選び方は $\displaystyle\binom{M}{K}$ 通り, 色の塗り方は $K! S_{2}(n,K)$ 通りです.
ただし, $S_{2}$ は第二種スターリング数です. あとは選ばれなかったボールの塗り方を決めればいいですが, これはどのように塗ってもいいので $M^{N-n}$ 通りです.
よって答えは
$$
\displaystyle\sum_{n=K}^{N}\displaystyle\binom{N}{n}\displaystyle\binom{M}{K}K! S_{2}(n,K)M^{N-n}
$$
です. 適切に前計算することで $O( (N - K) \log (N-K))$ で解くことができます.
提出：https://yukicoder.me/submissions/978372
