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

Binomial coefficients with constant "k"?
Автор Heisenbug, 10 лет назад, По-английски

Is there a stupid trick to calculate n-choose-k for a range of n with k always the same, which is faster than forming the full Pascal's triangle? With some fixed k, I need to calculate all n-choose-k modulo 10^9+7 for n up to 100,000 but there's no way I can calculate all the coefficients within 3 seconds.

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

»
10 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

C(N, K) = N! / (K! * (N — K)!) => C(N + 1, K) = C(N, K) * (N + 1) / (N + 1 — K), that's obvious.

I think, you don't know how to perform the division, so please read about modular multiplicative inverse.

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

You can divide by x over a prime modulus M by multiplying by xM - 2. This lets you use factorial formula for n choose k.

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

Well, for that task you don't even need the fact that K is constant, if you precalculate all the factorials, you can answer the nCk query in logarithmic time.

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

    Won't you answer the query in O(1) time then?

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

      Nope, you will need to calculate modular inverse(O(logN)).

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

        Actually, you can calculate modular inverse O(1) with O(n) pre-calculate.

        Let rv[x] is the inverse of x under M, then rv[x] = rv[M % x] * (M — M / x) % M and of course rv[1] = 1.

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

          That's awesome!! I'm eager to know why it works. Would you explain please?

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

            let M = kx + r, r < x, then k = M / x, r = M % x and

            both multiple rv[x] we will get

            so,

            → Ответить