phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

yukicoder No.1035 Color Box

問題

1~Nまでの異なる番号が書かれた箱に、M種類のペンキを使って塗りたい。
このとき、M種類すべてを使って、各箱は必ずいずれかの色に塗られているとする。
このとき、色の塗り方は何通りあるか?

制約

  • 1 <= M <= N <= 10^5

解法

N個をM個に割り当てる問題の場合、写像12相が考えられる。

この場合、区別するN個の玉を、区別するM個の箱に割り当てる問題として、各箱には1つ以上入れる場合になる。

式としては、包除原理から「Σ_{i=1}^M (-1)^{M-i} * Comb(M, i) * i^N」となる。