mochow's blog

By mochow, history, 9 years ago, In English

So again I am writing a post about ICL2015 Finals. My last post was about a DP problem which was not that much hard. But now I am really stuck by a tough problem (I am mentioning this one as tough because number of people who solved it was really low).

What I did for this one? Well, whatever I did to solve this problem was based on this tutorial from CodeChef. You can check that out.

In short the problem is:

Given n,k,m where n,k<=10^18, m<=10^6, we need to find C(n,k)%m where C(n,k) means number of ways to choose k objects from n objects.

So, the question is: What did I do to solve this problem?

Following the tutorial, I prime factorized m. Eventually, I got some prime numbers as factors. Then I applied Lucas' Theorem for each of this prime. After calculating answers for each of this prime, I had to solve some equations of the form X = A[i] (mod M[i]).

And these equations can be solved by Chinese Remainder Theorem.

Now, where did I get stuck? I did all these things mentioned above. But when we are given an m when m has prime powers in its factorized form, I could not find a solution to calculate the required result.

Let me give a quick example.

Imagine, n=10, k=5, m=12341. To find X=C(10,5)%12341, I first prime factorized 12341. So 12341=7*41*43.

I applied Lucas' Theorem for each of the prime factors. What I got is:

X = 0 (mod 7);
X = 6 (mod 41);
X = 37 (mod 43);

Now my task was to combine this equations to find our X. I applied CRT for this and got the required answer 252. Yahooo! :D

But wait, when m=1000 (or some number with prime powers), it didn't work. :(

This is where I need a solution. I actually need to calculate C(n,r)%m where m is of the form p^a where p is a prime.

As you can realize, I am not quite good. It will be too much helpful if you share your ideas on how to solve the above mentioned problem and give instructions to code it in detail, step by step. And I will be really grateful to you. :)

PS1: I found few ideas on how to get around this problem online. But I could not understand and of course could not code anything.

PS2: Really sorry for the long post.

Cheers and thanks in advance!
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Since the value of m is rather small I think this is what you need.

http://e-maxx.ru/algo/modular_factorial

Try reading this and give the problem another crack.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Sorry I did not understand how it can be helpful. :(

    Would you please explain?

    Thanks obviously. :)

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

Solution for this problem briefly discribed here in Russian. Anyway this might be useful.