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 a prime 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. :)

Sorry for the long post.

Cheers and thanks in advance!