VSQ2 - Editorial

general
, , , , , ,
1

Problem Link

Practice

Contest

Author: Abhishek Shankhadhar

Tester: Raju Varshney

Editorialist: Vaibhav Tulsyan & Raju Varshney

Difficulty

Easy

Pre-requisites

Derangements

Problem

Given a positive integer N, find the number of derangements of N.

Quick Explanation

The derangements of N can be represented by !N

!N = (N - 1) * (!(N - 1) + !(N - 2))

!0 = 1

!1 = 0.

Explanation

Formula 1:

!N = N! * \sum\limits_{i=0}^N \frac{(-1)^{i}}{i!}

Formula 2:

!N = (N - 1) * (!(N - 1) + !(N - 2))

!0 = 1

!1 = 0.

Proof for the recurrence

Precompute !N for all N in range [1, 10^{5}], modulo 10^9 + 7 using either formula.

1 Like
2

I did the same thing. But got WA for subtask 2.
Link of my solution: https://www.codechef.com/viewsolution/9982315

3

The problem is with (fact[n]/fact[i]) m . You need to multiply fact[n] by modular inverse of fact[i], instead of dividing fact[n] by fact[i]. This is a common property for the modulo operation, that (a / b) m is not equal to (a%m / b%m), it is equal to a * (b_inverse) % m.

1 Like
4

I memoized the exact recurrence…

https://www.codechef.com/viewsolution/9976031

5

Instead of using the concept of modular inverse or precomputing all factorial values, this problem can also be solved by directly precomputing possible derangement at given value of n using dynamic programming.Here is the link to my solution https://www.codechef.com/viewsolution/9984794

6

Well, that’s the same thing that I have posted! -_-

7

ohh yes…i haven’t seen that…