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!)$ ~\mathcal{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 \ge 2~, where $!0 = 1$ ~!0 = 1~ and $!1 = 0$ ~!1 = 0~

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

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

Comments

There are no comments at the moment.