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

Calculating (C(k, k) + C(k+1, k) + C(k+2, k) + ... + C(m, k)) modulo 1234567890 (m >= k) in 1 second?
Автор xuanquang1999, история, 8 лет назад, По-английски

Is there a way to do this if m, k <= 10^9?

PS: C here mean combination number.

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

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

Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).

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

Recall that C(K, K) + C(K + 1, K) + .. + C(M, K) = C(M + 1, K + 1)

Since your modulo is not a prime, you're probably looking to do something like this to compute it.

→ Ответить