• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            風雨

            驀然回首 卻在燈火闌珊處
            posts - 3, comments - 2, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

            [轉載] Computing n choose k mod p

            Posted on 2010-05-04 10:07 zgm 閱讀(579) 評論(0)  編輯 收藏 引用

            Computing n choose k mod p

            Postby joshi13 » Tue Apr 14, 2009 4:49 am

            Hi all.

            How can we apply the modular multiplicative inverse when calculating

            (n choose k) mod p, where 'p' is a prime number.

            If you could suggest some related problems, it would be very helpful.

            Thanks in advance.


            Re: Computing n choose k mod p

            Postby mf » Tue Apr 14, 2009 10:56 am

            You could use .


            Re: Computing n choose k mod p

            Postby maxdiver » Tue Apr 14, 2009 12:03 pm

            There is another, more "mechanical", but more general, approach. It can be applied to any formula containing factorials over some modulo.

            C_n^k = n! / (k! (n-k)!)
            Let's learn how to compute n! mod p, but factorial without factors p and so on:
            n!* mod p = 1 * 2 * ... * (p-1) * _1_ * (p+1) * (p+2) * ... * (2p-1) * _2_ * (2p+1) * (2p+2) * ... * n.
            We took the usual factorial, but excluded all factors of p (1 instead of p, 2 instead of 2p, and so on).
            I name this 'strange factorial'.

            If n is not very large, we can calculate this simply, then GOTO END_SCARY_MATHS :)
            If p is not large, then GOTO BEGIN_SCARY_MATHS:
            Else - skip the rest of the post :)

            BEGIN_SCARY_MATHS:
            After taking each factor mod p, we get:
            n!* mod p = 1 * 2 * ... * (p-1) * 1 * 2 * ... * (p-1) * 2 * 1 * 2 * ... * n.
            So 'strange factorial' is really several blocks of construction:
            1 * 2 * 3 * ... * (p-1) * i
            where i is a 1-indexed index of block taken again without factors p ('strange index' :) ).
            The last block could be not full. More precisely, there will be floor(n/p) full blocks and some tail (its result we can compute easily, in O(P)).
            The result in each block is multiplication 1 * 2 * ... * (p-1), which is common to all blocks, and multiplication of all 'strange indices' i from 1 to floor(n/p).
            But multiplication of all 'strange indices' is really a 'strange factorial' again, so we can compute it recursively. Note, that in recursive calls n reduces exponentially, so this is rather fast algorithm.

            So... After so much brainfucking maths I must give a code :)
            Code: Select all
            int factmod (int n, int p) {
               long long res = 1;
               while (n > 1) {
                  long long cur = 1;
                  for (int i=2; i<p; ++i)
                     cur = (cur * i) % p;
                  res = (res * powmod (cur, n/p, p)) % p;
                  for (int i=2; i<=n%p; ++i)
                     res = (res * i) % p;
                  n /= p;
               }
               return int (res % p);
            }

            Asymptotic... There are log_p n iterations of while, inside it there O(p) multiplications, and calculation of power, that can be done in O(log n). So asymptotic is O ((log_p n) (p + log n)).
            Unfortunately I didn't check the code on any online judge, but the idea (which was explained by Andrew Stankevich) is surely right.
            END_SCARY_MATHS:

            So, we can now compute this 'strange factorial' modulo p. Because p is prime, and we've excluded all multiples of p, then the result would be different from zero. This means we can compute inverse for them, and compute C_n^k = n!* / (k!* (n-k)!*) (mod p).
            But, of course, before all this, we should check, if p was in the same power in the nominator and denominator of the fraction. If it was indeed in the same power, then we can divide by it, and we get exactly these 'strange factorials'. If the power of p in nominator was greater, then the result will obviously be 0. The last case, when power in denominator is greater than in nominator, is obviously incorrect (the fraction won't be integer).

            P.S. How to compute power of prime p in n! ? Easy formula: n/p + n/(p^2) + n/(p^3) + ...


            (轉載:http://acm.uva.es/board/viewtopic.php?f=22&t=42690&sid=25bd8f7f17abec626f2ee065fec3703b
            久久99热只有频精品8| 国产激情久久久久影院| 亚洲伊人久久大香线蕉综合图片| 欧美牲交A欧牲交aⅴ久久| 国产国产成人精品久久| 久久久久亚洲AV成人网人人网站| 久久久久久伊人高潮影院| 久久久久久曰本AV免费免费| 精品国产婷婷久久久| 亚洲国产精品嫩草影院久久| 欧洲精品久久久av无码电影| 国产精品伊人久久伊人电影| av色综合久久天堂av色综合在| 99久久伊人精品综合观看| 国产午夜免费高清久久影院| 久久久久99精品成人片| 欧美伊香蕉久久综合类网站| 三级三级久久三级久久| 久久国产乱子伦精品免费午夜| 2021精品国产综合久久| 亚洲精品国产字幕久久不卡| 亚洲欧美一级久久精品| 久久综合给合综合久久| 国产巨作麻豆欧美亚洲综合久久 | 亚洲国产欧美国产综合久久| 久久久这里有精品中文字幕| 久久99精品国产麻豆婷婷| 久久久久国产一级毛片高清版| A级毛片无码久久精品免费| yellow中文字幕久久网| 午夜欧美精品久久久久久久| 亚洲av成人无码久久精品| 一97日本道伊人久久综合影院| segui久久国产精品| 国产亚洲美女精品久久久| 2020久久精品国产免费| 潮喷大喷水系列无码久久精品| 色婷婷综合久久久中文字幕| 伊人久久大香线蕉AV色婷婷色| 久久这里有精品| 国产成人精品久久|