yukicoder No.1035 Color Box - かんプリンの学習記録

問題概要

${1\le N\le 10^5}$ の異なる番号が書かれた ${N}$ 個の箱に ${1\le M\le N}$ 種類の色を塗る. このとき ${M}$ 種類全ての色を使い, 各箱を何かの色で塗るとき, 塗り方の総数を ${10^9+7}$ で割った余りを求めよ.

${N,M}$ がそこそこ大きいのでDPとかじゃなさそう. いい感じの組み合わせの式で表せないか考える.

${\downarrow}$

${N}$ 個の箱を区別できる ${M}$ グループに分けることと同じということがわかるので「けんちょんさんの素晴らしい記事」にある「区別できる玉を区別できる箱に1個以上いれる」方法であるので, 記事にあるような包除原理の公式

$\sum_{i=0}^{M}(-1)^{M-i}{}_{M}{\rm C}_{i}i^{N}$

が答えとなる. 計算量は ${O(M\log N)}$

包除原理の典型っぽかったので記事を書いた.