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」となる。