• <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 閱讀(566) 評論(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精品国产一区二区三区| 青青草国产成人久久91网| 99久久精品免费看国产免费| 国产精品gz久久久| 久久久久久久久66精品片| 精品一二三区久久aaa片| 99久久成人国产精品免费| 国产精品99久久精品爆乳| 精品多毛少妇人妻AV免费久久| 色婷婷综合久久久久中文| 久久精品无码一区二区三区免费| 国产精品久久久久久五月尺| 国产精品欧美久久久天天影视| 亚洲一区精品伊人久久伊人| 久久无码人妻一区二区三区| 久久精品国产亚洲沈樵| 人人妻久久人人澡人人爽人人精品| 国产精品福利一区二区久久| 亚洲精品午夜国产va久久| 成人午夜精品久久久久久久小说| 一本一本久久a久久综合精品蜜桃| 国产精品九九久久免费视频| 久久精品中文无码资源站| 亚洲国产成人久久一区久久| 国产精品99久久久久久宅男| 国产精品久久久久久福利69堂| 热久久视久久精品18| 精品国产青草久久久久福利 | 99久久精品免费看国产一区二区三区| 久久这里都是精品| 久久亚洲国产成人精品无码区| 久久精品国产亚洲欧美| 精品国产乱码久久久久久郑州公司| 狠狠色噜噜色狠狠狠综合久久 | 99久久久久| 久久精品国产亚洲一区二区| 97热久久免费频精品99| 久久无码人妻一区二区三区| 人人狠狠综合久久88成人| 一本色道久久综合亚洲精品|