No.391

問題も人も区別するので, 第二種スターリング数に $M!$ をかけたものを求めることになる.

包除原理を使うと計算式は

$$\sum_{i=0}^M (-1)^i {}_MC_i (M-i)^N$$

となる. プログラマを全問題に割り振る(担当者がいない問題がある場合もある)組み合わせの数 - プログラマを $M-1$ の問題に割り振る組み合わせの数 + プログラマを $M-2$ の問題に割り振る組み合わせの数…という感じ.

あとは以下の高速化を施せばいい.

• 累乗は繰り返し2乗法を使う.

• ${}_MC_i$ は $M$ が固定なので $i$ が増えるごとに更新する. 除算は逆元を使う.