I found a topics that nCr % P can be calculated in o(P) pre processing and lg(n) query.
I have no idea how it is done. Can anybody help me regarding this topics. Any idea, or any link. Thanks in advance.
I found a topics that nCr % P can be calculated in o(P) pre processing and lg(n) query.
I have no idea how it is done. Can anybody help me regarding this topics. Any idea, or any link. Thanks in advance.
CodeChef January Challenge problem "MTRICK"?
If my post somehow relates to that problem then I am sorry. It was not my intention. actually I am still stuck on this problem: http://codeforces.com/blog/entry/9697 Getting TLE. then I after a long time google search I found a topic that states something like this " nCr % P can be calculated in o(P) pre processing and lg(n) query." — Only states doesn't say how. I have a same post on TC forum "http://apps.topcoder.com/forums/?module=Thread&threadID=807841&start=0&mc=4#1828320". but the replies wasn't enough for me to get the idea. And that post on TC was quite before the contest you are talking about. Thank you.
I wrote a detailed blog on finding nCr mod a^p. It also contains details on Euclids and Chinese Remainder Theorems. Do give a good look and give a thumbs up if you like it. www.divyanshkumarsblog.wordpress.com
"No blog entry" it shows. Could you please update it?
I dont know its not working. Maybe a bug. Just copy paste for the time being.
What is nCr?
Also can be written C(n,r) which represent number of ways to choose r things from n things
sorry bad explanation . ya ,right , nCr means C(n,r).
For prime P it is easy to calculate — just apply Lucas theorem. (O(p·log(p)) preprocessing and log(n) by query)
Otherwise, express P as p1a1·...·pkak, calculate C(n, k) modulo piai and get the answer by chinese remainder theorem.
Calculating C(n, k) mod pa, as far as I understood from this paper, are not so easy.
Are you sure that modulo is not prime?
Yes I am sure the modulo is not prime. http://www.lightoj.com/volume_showproblem.php?problem=1318 This is the actual problem where i was thinking to implement that idea. Coz, I have tried all possible C(n,r)%P that i knew, but got TLE. In lucas theorem and all others theorems I have seen , all starts with assuming P prime. :(
OK, maybe it will help:
C(n, k) mod pa can be computed in O(p·log(n)) time:
Calculate the largest b, such that C(n, k) = 0(mod pb)
How to calculate n!! mod pa where n!! is the largest divisor of n! coprime with pa?
n!! = (1·2·...·p - 1·1)·(1·2·...·p - 1·2)·...(1·2·...·n mod p)
We can see that n!! mod pa = (p - 1)![n / p]·(1·2·...·n mod p)·([n / p]!! mod pa)
Answer is C(n, k) = pb · n!! · inverse((n - k)!!) · inverse(k!!)
Finally, you can precalculate all factiorial up to (p - 1)! modulo pa and answer the queries in O(log(n)2) time.
Thanks all ... specially PavelSavchenkov. Solved and learned.
if we take p=2, won't n!!mod p^a always give 1??(irrespective of even a)
How calculate the largest b, such that C(n, k) = 0(mod p^b) ?
You can count, how often the prime p appears in C(n, k). C(n, k) = n! / k! / (n-k)!. So you just need to count, how often p appears in n!, in k! and in (n-k)!.
The expression from pavel.savchenkov's comment about n!! is incorrect
n!! = (1·2·...·p - 1·1)·(1·2·...·p - 1·2)·...(1·2·...·nmodp)
It doesn't make sense here to rewrite all the numbers mod p if you want to get the answer mod pa.
Any idea for (n!)modpa, where p is a prime number??
Found it: https://es.wikipedia.org/wiki/Teorema_de_Wilson
I could not find anything that proves
n!! = (1·2·...·p - 1·1)·(1·2·...·p - 1·2)·...(1·2·...·nmodp)
I am not getting why we are taking mod p when we need to find n! mod p^a.
How to find inverse modulo (pa). Please, someone explain it. Edit : Got it. a - 1 ≡ (a mod m) - 1 (mod m). So we can calculate a mod m and then use extended euclid's to find the inverse.
how do you calculate when p is not square free ?
I_Love_Shristi what is m here? Is it p^a ?
can you take an example to explain?
What is the logic behind taking n!!?
Great approach based on Wilson's theorem but how can i find inverse(n)!!
The generalized Lucas Theorem isn't all that hard after all. After three days of pondering and reading I finally implemented it. Take a read here.
I submitted this problem in the codechef problem SANDWICH from May challenge and got AC.
"For prime P it is easy to calculate — just apply Lucas theorem (O(p·log(p)) preprocessing ". How ?? precalculating this will take O(p^2)memory and time.
This blog is related to problem in running contest.
This blog created 3 years ago....
But people are discussing now......
백준 1등 쿠사가님 평소에 블로그 잘 보고 있습니다. pavel.savchenkov의 코멘트에 대해서 혹시 설명해주실 수 있으신가요..? 지금 거의 이틀째 nCr mod p^q에 대해서만 보고 있는데 이해가 될만한 문서를 찾지를 못하겠네요.
도와주세요! ㅠㅠ 어떻게 하면 저 과정으로 정답이 성립되는 걸까요? n!! = (1·2·...·p - 1·1)·(1·2·...·p - 1·2)·...(1·2·...·n mod p) << 왜 이런식을 가지는지랑 we can see that으로 넘어가는 부분이 이해가 잘 안가네요. 제발 도와주세요.
쿠사가님 블로그덕분에 이항계수 5번문제까지는 풀었는데, 6번문제를 풀려면 이 이론을 알아야하는데 쉽지가 않네요. 감사합니다.
I didn’t tried to understand pavel.savchenkov‘s reply, and I don’t know why you are asking me here.
Also, you don’t need that knowledge to solve that problem.
I'm sorry for being rude. Because of my bad English and Because I learned binomial coefficient on your tistory, I was glad to see you on this post. That's it. Sorry. Thank you for your comment.
Really? I think this is bad when the question directly solves the problem or it's too obvious that someone is asking about the problem, but this not happen here ... o wait maybe it happen now, you posted the problem!
I wrote a detailed blog on finding nCr mod a^p. It also contains details on Euclids and Chinese Remainder Theorems. Do give a good look and give a thumbs up if you like it.
Divyansh Kumar's Blog