Блог пользователя DonMichaelCorleone

How to calculate (a! / b!) % mod
Автор DonMichaelCorleone, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
9 лет назад, # |
← 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. :)

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    How to build segtree in O(n) time?

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

    → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 5   Проголосовать: нравится +30 Проголосовать: не нравится

      There is a way of building sparse table in 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 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

      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 :

      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 or whole interval [A;B] is in or so you can move here to answer query thus having O(h) time complexity, where h is

      Possible O(1) solution

      Hope this helps you!

      → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If mod is not very big, you can do it in time where M = mod.

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

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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
      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        120 / 720 is not 0.

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

          → Ответить
»
9 лет назад, # |
← Rev. 5   Проголосовать: нравится -13 Проголосовать: не нравится

I gave a wrong answer! Sorry

→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится -26 Проголосовать: не нравится

...

→ Ответить