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.

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 210 |

2 | awoo | 188 |

3 | Errichto | 186 |

3 | rng_58 | 186 |

5 | SecondThread | 182 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 172 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/06/2021 04:33:39 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Pit is easy to calculate — just apply Lucas theorem. (O(p·log(p)) preprocessing andlog(n) by query)Otherwise, express

Pasp_{1}^{a1}·...·p_{k}^{ak}, calculateC(n,k) modulop_{i}^{ai}and get the answer by chinese remainder theorem.Calculating

C(n,k)modp^{a}, 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)modp^{a}can be computed inO(p·log(n)) time:Calculate the largest

b, such thatC(n,k) = 0(modp^{b})How to calculate

n!!modp^{a}wheren!! is the largest divisor ofn! coprime withp^{a}?n!! = (1·2·...·p- 1·1)·(1·2·...·p- 1·2)·...(1·2·...·nmodp)We can see that

n!!modp^{a}= (p- 1)!^{[n / p]}·(1·2·...·nmodp)·([n/p]!!modp^{a})Answer is

C(n,k) =p^{b}·n!! ·inverse((n-k)!!) ·inverse(k!!)Finally, you can precalculate all factiorial up to (

p- 1)! modulop^{a}and answer the queries inO(log(n)^{2}) time.Thanks all ... specially PavelSavchenkov. Solved and learned.

can u help in code?im unable to do @najim4689

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 incorrectn!! = (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

pif you want to get the answer modp^{a}.Any idea for (

n!)modp^{a}, 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 (

p^{a}). Please, someone explain it. Edit : Got it.a^{ - 1}≡ (amodm)^{ - 1}(modm). So we can calculateamodmand 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