I did it using inclusion exclusion principle here ie we distribute balls( = n-k) into boxes ( ceil(n/k) ) with maximum of k balls in each box and to calculate this I used 1. Lucas Theorem 2. Chinese Remainder Theorem. The approach for this is explained here (Q.2 - Life is Strange 4th subtask).
But sadly I could pass only 3 subtasks, I couldn’t figure out the shorter version of formula.
Link for my solution.
1 Like
I have used Generalized Lucas theorem and CRT to solve the problem using the same paper mentioned by some users who have already answered in this thread. I don’t know why I get WA on only 1 test case. Throughout the contest I have had 30 submissions for this problem with different changes in code to avoid overflows and all but I still could not get it. Please, can someone tell me what is wrong with my code? Thank you in advance to anyone who tries to look through my code. 
Solution: CodeChef: Practical coding for everyone
@ista2000 WA was because of overflow only!!
See this:
https://www.codechef.com/viewsolution/13632506
There was overflow happening where you calculate the value of ret in f function.
I just placed %x more cautiously.
1 Like
Here you can find a decent explanation and code in c++ and python for the nCr (large n and r) problem which includes handling the case of prime powers :). I also found the paper by Andrew Granville which seems to explain the same but it was too complex for me to understand.
I used the code found in this link but gave the guy full credit in the code :). I learned something in this contest which is cool :).
Hope it helps.
http://m00nlight.github.io/algorithm/2015/04/11/hackerrank-ncr
1 Like
1 Like
Given N,K
Now, minimum number of partitions you can have is P = ceil(N/K),
Now what is the maximum size of sandwich can be made with P partitions ?
That is P*K, suppose initially all partitions are full, for example if N=10 and K=4, we have P=3
and partitions are like this :
|…|…|…| now we have 3 groups each is fully filled.
Now coming to the question,
we need to delete some ‘.’ from these groups in order to get a valid configuration in which total size of sandwich is N, suppose if we add a ‘X’ to any group we reduce its size by 1. Now the current size is P*K and required size is N, so we need to distribute (P * K - N) ‘X’ (s) to these P groups, if you observe R = (P * K - N) = (K - N % K), and now our problem is reduced to finding ways of distributing R things in P groups ( any group can get 0 ‘X’ ) for which you can compute the binomial coefficient C(P+R-1,P-1).
Hi guys!
Here is a video editorial by @jtnydv25 on the problem.
It uses Number Theory and the Chinese Remainder Theorem to get to the solution. Feel free to leave your doubts and suggestion in the video comments.
3 Likes
There was similar problem on hackerank. And the link is editorial to that problem which gives detailed explanation about how to implement ncr % m, whether m is prime or composite;
Ratings haven’t updated.
1 Like
But CRT only works for square free numbers right?
Ik, just in case he read that after the ratings were updated, it would’ve been weird.
I am not quite sure , but i think CRT works fine if N and m are co- prime.
See the link in source.
Here’s a quote from that link:
“You can find the result of nCr % m for each m = 27, 11, 13, 37. Once you have the answers, you can reconstruct the answer modulo 142857 using Chinese Remainder Theorem. These answers can be found by Naive Methods since, m is small.”
how do u calculate ans modulo all prime powers in M .??
Since prime power can be non prime ( i am assuming prime power means p^q)
So denominator and prime power can be non co prime too right ??
So how do you calculate modular inverse !!
1 Like
Yes N and K are not 10^18 in that testcase.
how ?? p^q is non prime right ?? lucas theorem works for only prime modulus right ?? Correct me if wrong !!
Can you please provide some source to read about Lucas Theorem and CRT?
so constraints were n,k <= 10^18 or the same as of subtask ,2??
How did you identify that (nk−n%k+knk)(nk−n%k+knk) is the solution? I would appreciate if you can explain that as well 
1 Like