For 50 pts : Python users could use this inbuilt function scipy.misc.comb(N, R, exact=True) as mentioned in my solution : Python
However for 100 pts the topic involved were 1. Lucas Theorem 2. Chinese Remainder Theorem 3. Wilson Theorem which gave an AC and can be referred by link mentioned in my Java code : here
PS !! Test cases were again weak !!
Passed subtask c ( M is prime ) in O(k) using normal nCr dp and biginteger in java !!
Two more links:
Combinatorics - Mathematics Stack Exchange:
nCr - HackerRank:
http://m00nlight.github.io/algorithm/2015/04/11/hackerrank-ncr
I didn’t use lucas theorem. I just solved it using CRT and by finding Modular multiplicative inverses.
Let n=⌈N⁄K⌉
and x = (K × n) - N
So, as we have to distribute x vacancies in n parts, the number of ways is n+x-1Cx
Let the prime factorization of M = p1e1×p2e2×p3e3×p4e4 …×ptet
Here t is the total no of unique prime factors.
Here piei and pjej are coprime for any 1 ≤ (i≠j) ≤ t
So if we find n+x-1Cx Mod piei for each i,
We can then combine the results to find n+x-1Cx Mod M using CRT
Note that if x! and (n-1)! don’t have any factors of pi then they would have unique
modular multiplicative inverse.
The main issue that we face now is that (n-1)! and x! could have factors of pi
Let y be the highest power of pi which divides x!
Then let F(x,piei) = ((x!)/piy) Mod piei
As F(x,piei) is not divisible by pi, we can find its modular multiplicative inverse.
We can later on deal with the total power of pi in n+x-1Cx and multiply it to our answer.
So n+x-1Cx Mod piei will be (piz × F(x+n-1,piei))/(F(x,piei) × F(n-1,piei)) Mod piei
Here z is the highest power of pi which divides n+x-1Cx
To find F(x,piei), the trick here is to take all the numbers divisible by pi out of the factorial.
Notice that we take out precisely (⌊x⁄pi⌋!)×pi⌊x⁄pi⌋ out of the factorial.
Now let H = x!/((⌊x⁄pi⌋!)×pi⌊x⁄pi⌋) Mod piei
(Note: H is basically x! with all terms divisible by pi ignored)
H can be found in in O(piei+ log x) using fast exponentiation as
all numbers in the factorial repeat after piei numbers Mod piei
Now we can say that F(x,piei)=H×F(⌊x⁄pi⌋,piei)
This is a recurrence relation, so the over all complexity is O((piei+log x)×(log x))
We now know how to find F(x,piei)
Now we need to know how to find the power of pi in x!.
This is simply Σ ⌊x⁄pic⌋ where c is a natural number.
Here is my solution - CodeChef: Practical coding for everyone
PS:- The recursive part can be optimized by making it iterative.
That reduces the overall complexity to O(M + (log2(N+k)×(log M)))
Nobody seems to have shed some light on how to calculate \binom{a}{b}\ mod\ (p^k). We don’t need any research paper to calculate that just some group theory. First let us get rid of all the prime powers of p in \binom{n}{r}. Now let us consider a finite group where X = \{ x : x < p^k, gcd(x, p^k) = 1 \}. Now we can see that this is abelian group [commutative group] under multiplication. So, we can see that if we multiply all the elements of this group and take mod\ (p^k)\ i.e\ x_1.x_2.x_3...x_i.. = -1\ if\ p^k = 4\ or\ p^k\ is\ power\ of\ odd\ prime\ and\ +1\ otherwise. Now to calculate n!\ mod\ p^k[remember we’ve got rid of all the prime powers earlier], we see n!\ \equiv (\pm 1)^{\dfrac{n}{p^k}}.(1.2.3..(n\ mod\ p^k)). (n / p)!\ (mod\ p^k). This is a simple recursive equation which we can calculate in O(p^k\ log\ n) time. Similarly calculate (n - r)!\ \&\ (r!). Take their inverses using extended euclidean and apply chinese remainder theorem.
For
Subtask 1:
Brute force nCr calculations would work. No overflow worry. Easy 10 points.
Subtask 2 and 3:
For prime M, Lucas theorem([Lucas Theorem][1])
and for non prime M, DP based method to calculate nCr will work([DP-nCr][2])
Subtask 4:
Requires complete implementation of Chinese Remainder Theorem.
@shashank96,(https://discuss.codechef.com/questions/98129/your-approach-to-solve-sandwich?page=1#98152)
I derived that formula so I can shed some light on the approach.
Lets take n=13,k=4.
then one such way to distribute this is:
4|4|4|1
Now, we can move some of the value from the first 3 slots to the last slot ‘1’.
we can add a max value of 3 to the last slot since 1+3=k and we cannot have a piece with >k length.
So, by using multinomial theorem,we need to find solutions to:
x1+x2+x3<=3
which is the same as x1+x2+x3+x4=3.
Also the limits for xi can be take to be infinity since their upper bound is greater than the value on RHS.
We know that the formula for non-negative solutions of x1+x2+x3…+xm=p is:
(p+m-1)C(m-1)
Its easy to see that m=(ceil(n/k)) and p=(k-n%k).
Only two special cases:
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.
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.
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
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.
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.
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 !!