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 | tourist | 3496 |

2 | Um_nik | 3337 |

3 | Petr | 3298 |

4 | W4yneb0t | 3218 |

5 | Radewoosh | 3216 |

6 | OO0OOO00O0OOO0O0…O | 3188 |

7 | Syloviaely | 3168 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | fateice | 3099 |

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

1 | tourist | 185 |

2 | rng_58 | 170 |

3 | csacademy | 165 |

4 | Petr | 158 |

5 | Swistakk | 153 |

6 | lewin | 148 |

7 | Errichto | 147 |

8 | matthew99 | 145 |

9 | Zlobober | 141 |

9 | adamant | 141 |

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/18/2018 07:49:58 (d2).

Desktop version, switch to mobile version.

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. Divyansh Kumar's Blog

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

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 ?

RickGrimes what is m here? Is it p^a ?

can you take an example to explain?

What is the logic behind taking 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