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 | 3602 |

2 | Petr | 3294 |

3 | moejy0viiiiiv | 3240 |

4 | TakanashiRikka | 3178 |

5 | W4yneb0t | 3162 |

6 | LHiC | 3149 |

7 | Um_nik | 3148 |

8 | izrak | 3109 |

9 | ershov.stanislav | 3105 |

10 | Radewoosh | 3094 |

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

1 | rng_58 | 182 |

2 | Errichto | 167 |

3 | csacademy | 166 |

4 | Petr | 162 |

5 | tourist | 157 |

6 | Swistakk | 155 |

7 | Zlobober | 147 |

8 | zscoder | 144 |

9 | matthew99 | 141 |

10 | GlebsHP | 138 |

10 | Radewoosh | 138 |

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

The only programming contests Web 2.0 platform

Server time: Jul/24/2017 09:36:46 (c2).

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.

This blog is related to problem in running contest.

This blog created 3 years ago....

But people are discussing now......

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