Блог пользователя najim4689

Автор najim4689, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

CodeChef January Challenge problem "MTRICK"?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.me/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.

»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

What is nCr?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

      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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "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.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This blog is related to problem in running contest.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    This blog created 3 years ago....

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      But people are discussing now......

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится

        백준 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번문제를 풀려면 이 이론을 알아야하는데 쉽지가 않네요. 감사합니다.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    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!

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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