How to calculate (a! / b!) % mod

DonMichaelCorleone's blog

By DonMichaelCorleone, history, 8 years ago, In English

How to calculate (a! / b!) % mod where n is 1<=n<=20000000, m is 1<=m<=n and mod is a positive integer ?

number theory, factorial, combinatorics, modular arithmetic

DonMichaelCorleone
8 years ago
19

Comments (19)

Write comment?

satyaki3794

8 years ago, # |

← Rev. 3 →

+12

If you want to avoid multiplicative inverses, as the limits are <= 2e7, you can create a segment tree. If you divide a! by b!, you want to multiply the numbers b+1, b+2,....a. You can use a segment tree to do each query in O(logn), after building the segtree in O(n). You can also use a sparse table (similar to that explained in this [Topcoder tutorial](https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Sparse_Table_(ST)_algorithm)) to speed it up and solve each query in O(1), after preprocessing in O(n*logn). Note that this approach will work due to low limits (2e7).

UPD: The sparse table approach will also be O(logn) and not O(1). See FatalEagle's comment. :)

→ Reply

Velter

8 years ago, # ^ |

← Rev. 2 →

How to build segtree in O(n) time?

UPD. Yes, O(4*N) = O(N). My mistake.

→ Reply

P_Nyagolov

8 years ago, # ^ |

Segment tree is usually built in O(N) — it is a simple dfs.

→ Reply

FatalEagle

8 years ago, # ^ |

+24

Can you describe the sparse table approach in more detail? The one in the tutorial seems to rely on the fact that counting the same element twice in the min function won't change the result.

→ Reply

satyaki3794

8 years ago, # ^ |

Aah, right. My bad. The sparse table approach will also be logn, and not constant time, due to the reason you pointed out above. :)

→ Reply

koamy

8 years ago, # ^ |

← Rev. 5 →

+30

There is a way of building sparse table in $\text{[math]}$ so that you won't have to consider element twice.

I'm not completely sure that this is called sparse table, but as far as Burunduk1 told me, it has something to do with it.

You have to do something like Divide & Conquer optimization.

Consider that you now need to precalc something for the interval [L;R] You should take $\text{[math]}$ and calculate answers for queries [M;M], [M;M + 1], ..., [M;R] Calculate same thing for queries [M - 1;M - 1], [M - 2;M - 1], ..., [L;M - 1]

Now you can answer any query [X;Y], such that X ≤ M ≤ Y if you can merge answers for [X;M - 1] and [M;Y] in O(1)

Now we can deal with any query that consists M and we have to deal with intervals [L;M - 1] and [M + 1;R].

We have wasted O(R - L) calculation time, so whole recursion will be $\text{[math]}$

I don't remember exactly how do we make it run in O(1) from this point, but should be possible with some bit manipulation.

Here's the solution in $\text{[math]}$ :

Note that you can do it like on a segment tree now, when you are in some node [L;R] and want to process interval [A;B] you need to either answer the query instantly if $\text{[math]}$ or whole interval [A;B] is in $\text{[math]}$ or $\text{[math]}$ so you can move here to answer query thus having O(h) time complexity, where h is $\text{[math]}$

Possible O(1) solution

Hope this helps you!

→ Reply

Vivek1998299

6 years ago, # ^ |

← Rev. 4 →

-10

if anyone has any doubt regarding the implementation of the above method can refer this: https://discuss.codechef.com/questions/116992/disjoint-sparse-table

Along with O(logN) solution , it also discuss an O(1) solution. We however cant update it. It can replace segment tree if no updates are required.

Hope this helps!! Thank you!!

→ Reply

KarlisS

6 years ago, # ^ |

There is a simple way of getting table for inverse of factorials partially avoiding inverse calculation. If you have n!^- 1 then (n - 1)^- 1 = n!^- 1·n. n!^- 1 can be either precalculated or calculated the normal way if you want O(n + q) instead of O(n + qlogn). I think there was some other method of calculating inverse for all numbers from 1 to n or their factorials in O(n) but it required a bit more of number theory knowledge to understand and I can't remember it.

→ Reply

BekzhanKassenov

8 years ago, # |

If mod is not very big, you can do it in $\text{[math]}$ time where M = mod.

Here's link, but unfortunately it's only in Russian.

→ Reply

unprost

8 years ago, # |

← Rev. 2 →

If (a < b) answer is 0, if (a == b) answer is (1 % MOD), otherwise Product(b+1, a) % MOD

Imagine you have number A, module M, and remainder C:

A % M = C
A / M = k
A = M*k + C
A * B = (M*k + C) * B
A * B = M*k * B + C * B
(A * B) % M = (M*k * B + C * B) % M
(A * B) % M = (M*k * B) % M + (C * B) % M
(M*k * B) % M = 0
(A * B) % M = (C * B) % M

Now you need a multiplication loop (b .. a] taking module on every step

→ Reply

Velter

8 years ago, # ^ |

if(a < b) answer isn't zero.

For example, 5!/6!(mod 1e9+7) = 36166666920

→ Reply

unprost

8 years ago, # ^ |

Sorry, than what does the exclamation sign means here? I thought that it's factorial:

(5! / 6!) % (1e9 + 7) = 
(120 / 720) % (1e9 + 7) = 
( 0 ) % (1e9 + 7) = 0

→ Reply

Na2a

8 years ago, # ^ |

120 / 720 is not 0.

→ Reply

unprost

8 years ago, # ^ |

It's not 0, but mathematical modulo operation is applicable only for integer division, so the answer must be integer

By the way, in the condition, I think, that 'a' is meant to be 'n', and 'b' is meant to be 'm'. So there is a rule, that 1 <= m <= n, and (a < b) can be a valid input

→ Reply