Editorial for SAC '22 Code Challenge 5 P3 - Querying Presents - Olympiads Online Judge

Editorial for SAC '22 Code Challenge 5 P3 - Querying Presents

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

Subtask 1

It suffices to loop through every possible permutation of students and increment a counter by $1$ $1$ if the current permutation assigns every number to a different number than its index.

Time Complexity: $\mathcal{O}(N!)$ $O (N!)$

Subtask 2

Realize that (through either OEIS or previous problems) this is counting derangements, which has the following recurrence:

$!n = (n-1)(!(n-1) + !(n-2))$ $! n = (n - 1) (! (n - 1) +! (n - 2))$ for $n \ge 2$ $n \geq 2$ , where $!0 = 1$ $! 0 = 1$ and $!1 = 0$ $! 1 = 0$

Compute this for each query (or precompute for $N \le 10^6$ $N \leq 10^{6}$ ) while $\bmod 10^9 + 7$ $mod 10^{9} + 7$ .

Time Complexity: $\mathcal{O}(\sum_{i=1}^T N_i)$ $O (\sum_{i = 1}^{T} N_{i})$

Comments

There are no comments at the moment.