### Duelist1234's blog

By Duelist1234, history, 3 months ago,

In yesterdays Div 2 C a part of the solution required to divide factorials. Know you might think that that is easy , but ofcourse , there was just one thing screwing everything up , mod 10^9+7. Just one number ruined everything. And thats why im asking , how to divide factorials properly when you take their mod first?

• 0

 » 3 months ago, # |   0 I don't think factorials is necessary in the Problem C
 » 3 months ago, # |   +23
•  » » 3 months ago, # ^ |   +33 Cool video, thanks!
•  » » » 3 months ago, # ^ |   +6 Yeah , i now completely understand modular inverse after watching , shame he stopped posting.
•  » » » » 3 months ago, # ^ |   +48 Yeah, ikr. I really wish he'd post more.
•  » » » » » 3 months ago, # ^ |   0 Why did you stop posting? :(
•  » » 3 months ago, # ^ |   +3 Thanks , I got ac.
 » 3 months ago, # |   +30 The theorem can be found on this Wikipedia link. It says $a^p \equiv a \mod p$ where $p$ is a prime number. Thus you can think of the fact that $a^{p - 1} \equiv 1 \mod p$ and then $a^{p - 2} \equiv a^{-1} \mod p$. Thus by multiplying by $a^{p - 2}$ you essentially divide by $a$. To calculate $a^{p-2}$ fast you can use some version of fast exponentiation algorithm.
 » 3 months ago, # | ← Rev. 2 →   0 As someone already pointed out, you can use Fermat’s little theorem to do this under a prime modulus.Although it might interest you to know that a DP solution for that problem also exists. Every time you make a move, you get rid of 1 row and 1 column, and the computer gets rid of the other row and column: in total, you remove 2 rows and columns. Except when your move is of the form $(r, r)$ in which case you only remove 1 row and column.Imagine trying to place a rook in $(r, r)$. Now you’ve essentially reduced your problem to finding the number of ways to place rooks in an $(n-1)\times(n-1)$ grid. Also, you can place it on $(a,b), a \neq b$, where you have $2n$ choices, subtract the one where you have the same row and column to get $2n-1$ cases. This gets rid of two rows and columns.So $dp[i] = dp[i-1] + (2i - 1) dp[i-2]$. The base cases are $dp[0]=dp[1]=1$.
 » 3 months ago, # | ← Rev. 2 →   +1 I would like to add that in the more general case, when you want the inverse of a factorial (or any integer n) modulo a number m that is not a necessarily a prime but whom you know the factorization, you simply use the euler theorem and put n at the power $\phi(m)-1$.The other solution is to use the extended Euclidean algorithm on n and m, which will return u and v such that nu+mv=gcd(n,m), in other word u will be the inverse of n mod m if n and m are coprime. An other point is when you want the inverse of every factorial up to n! it can be to costly to compute each inverse, compute just $(n!)^{-1}$ and then use $(i!)^{-1}=(i+1)((i+1)!^{-1})$, you can even get every $i^{-1}$ by using $i^{-1} = (i!)^{-1} (i-1)!$