najim4689's blog

By najim4689, 3 years ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

CodeChef January Challenge problem "MTRICK"?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

What is nCr?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also can be written C(n,r) which represent number of ways to choose r things from n things

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry bad explanation . ya ,right , nCr means C(n,r).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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. :(

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 5   Vote: I like it +8 Vote: I do not like it

      OK, maybe it will help:

      C(n, kmod 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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks all ... specially PavelSavchenkov. Solved and learned.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if we take p=2, won't n!!mod p^a always give 1??(irrespective of even a)

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        How calculate the largest b, such that C(n, k) = 0(mod p^b) ?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)!.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you take an example to explain?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What is the logic behind taking n!!?

  • »
    »
    13 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

This blog is related to problem in running contest.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    This blog created 3 years ago....

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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!

»
13 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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