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
I did the same thing. But got WA for subtask 2.
Link of my solution: CodeChef: Practical coding for everyone
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 CodeChef: Practical coding for everyone
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
Well, that’s the same thing that I have posted! -_-
ohh yes…i haven’t seen that…