Editorial

ある数列$P$について$P_i = i$番目の人がもらった手紙の番号としたとき、この問題で求めるものは以下のように言い換えることができます。

• 1つ以上の$i \ (1 \le i \le N)$について$P_i = i$なる要素が存在する場合の数

これを直接考えるのはとても面倒なので余事象を考えてみます。

• 数列$P$の任意の$i$について$P_i \neq i$が成り立つ場合の数

ここで「$i$番目の手紙は人$i$に届くはずだった。」ということから数列$P$の中には$1, 2, ..., N$までの数字が1つずつ存在することを考えると数列$P$は順列であることがわかります。 したがって余事象は

• 長さ$N$の順列$P$における完全順列の個数

と言い換えることができます。

長さ$N$の完全順列の個数を$a_n$と置くと$N = 1$のとき$a_1 = 0$, $N = 2$のとき$a_2 = 1$, $N \ge 3$のとき$a_n = (n-1)(a_{n-1}+a_{n-2})$として求めることが可能です。(モンモール数)

また、長さ$N$の順列の総数は$N!$です。

したがって、求める答えは$N! - a_n$です。 $N!$と$a_n$はそれぞれ$O(N)$で求めることができるので、この問題を$O(N)$で解くことができました。

実装例(C++)

実装例(Python)