Duelist1234's blog

Dividing factorials
By Duelist1234, history, 6 months ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think factorials is necessary in the Problem C

→ Reply
»
6 months ago, # |
  Vote: I like it +23 Vote: I do not like it

AlgorithmsThread 1: Division Under Mod!

→ Reply
»
6 months ago, # |
  Vote: I like it +30 Vote: I do not like it

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.

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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$$$.

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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)!$$$

→ Reply