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
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 !!
@sanket407 nCr % p^q has to be calculated using Lucas theorem for prime powers
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
Thank you ymondelo20
@c0d3h4ck3d Updated the answer with resources for both.
@vijju123 It was more of an observation, after writing a brute force algorithm.
it is, but in a paper of Andrew Granville, it has been extended to prime powers, and after that u need to use chinese remainder theorem