xuanquang1999's blog

Calculating (C(k, k) + C(k+1, k) + C(k+2, k) + ... + C(m, k)) modulo 1234567890 (m >= k) in 1 second?
By xuanquang1999, history, 8 years ago, In English

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

PS: C here mean combination number.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +25 Vote: I do not like it

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.

→ Reply