No.009 C

まず, $N$ 人から間違えた手紙を渡された $K$ 人を選ぶ組み合わせの数は $S_1 = {}_NC_K$ である.

次に $K$ 人がすべて間違えた手紙を渡される組み合わせの数は, 包除原理を使って,

$$S_2 = K! - \sum_{i=1}^{K-1} (-1)^{i+1} {}_KC_i(K-i)!$$

となる. $S_1S_2$ が答えである.

ここで, $S_2$ は $K$ までの階乗と逆元を計算しておけば, $O(K)$ で計算できる.

$S_1$ は $K$ が小さいので, $N(N-1)\cdots(N-K+1)/K!$ で計算すれば $O(K)$ で計算できる.