kfoozminus's blog

Problem about sum of nCr % M, when n > M (Dhaka Regional 2013)
By kfoozminus, history, 8 years ago, In English

This problem's solution ends up at

nCr(A+B-i, i) * nCr(A+B-2i, A-i) * pow(x, A-i) * pow(y, B-i) * pow(z, i) ; for every 0 <= i <= min(A, B)

All inputs are between 1 and 10^17 inclusive, and result should be printed as (result % M); where M = 1e6 + 3

I've seen a solution like this

while(A || B)
{
        u = A % M;
        v = B % M;
        tmp = 0;
        for ( i = 0; i <= min(u, v); i++)
        {
                tmp = (tmp + nCr(u+v-i, i) * nCr(u+v-2i, u-i) * pow(x, u-i) * pow(y, v-i) * pow(z, i)) % M;
        }
        ans = (ans * tmp) % M;
        A /= M;
        B /= M;
}

Full Source Code: link

Can you please explain how did he derive this?

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

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

https://en.wikipedia.org/wiki/Lucas%27_theorem

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I'm sorry, I still don't understand. Lucas says to express n and r in base-M.

    Here, it looks like A and B is converted into M-based. A % M and B % M is applied to the whole term, not just nCr part. I'm sorry, I'm not getting it. Could you please give a better look and explain?

    Thanks in advance.

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

The problem asks to calculate weighted Dellanoy numbers. This article (page 22) references a proof of their Lucas' theorem analog.

→ Reply