### habib_rahman's blog

By habib_rahman, history, 5 years ago,

Given N distinct integers from 1 to N, you have to find the number of ways the N integers can be rearranged in M empty slots such that, no integer matches with its slot index. Note that, slots are indexed from 1 to M.

Print the number of ways modulo 23377788.

0<=N<=M<100000 and It has 200 test cases.

I came up with a solution like this but not sure its correct or not. And have not any idea to modulu it by non prime.

• -7

 » 5 years ago, # |   -10 Auto comment: topic has been updated by habib_rahman (previous revision, new revision, compare).
 » 5 years ago, # |   0 Modulo operations like addition/multiplication are done the same way as in primes. For modulo inverse, you must be careful. Note that if the number you want to find the inverse is not coprime with the mod, then there is no solution. Otherwise just calculate this number raised to the (phi(mod) — 1) power, this follows from euler's theorem.
•  » » 5 years ago, # ^ |   0 Also, extended Euclidean algorithm can be used be calculate inverse.
•  » » » 5 years ago, # ^ |   -10 I need the solution of the problem also.
 » 5 years ago, # | ← Rev. 2 →   0 For n ≤ M we have M - 1 variants, for n > M we have M variants. You just need two involutions by modulo and operation like ab % MOD.
•  » » 5 years ago, # ^ |   -10 A little bit explanation please.
•  » » » 5 years ago, # ^ |   0 Lets consider arbitrary number n. We have only one restriction: n cannot be matched with n-th box. From the statement we know that number of boxes greater or equal to any n, thus number of ways to correctly put n to some box is M - 1 (we may put n to any box except n-th box). Total number of rearrangments is (M - 1)N % MOD. All you need is multiplying two numbers by modulo.
•  » » » » 5 years ago, # ^ |   -10 So, for N = 2 and M = 3 your answer will be 4. But, it should be 3
 » 5 years ago, # |   +6 You can use in Codeforces.\frac{N!}{(M-N)!}\times \sum_{i=0}^N (-1)^i\frac{(M-i)!}{i!(N-i)!} Add dollar sign in both sides.
 » 5 years ago, # |   +5 I think you can use Chinese remainder theorem to solve your problem.
•  » » 5 years ago, # ^ |   -10 Please share your idea. Thanks in advance.
 » 5 years ago, # |   0 While it doesn't answer the general question, you can read more about derangements (permutations where ) here:https://en.wikipedia.org/wiki/Derangement