• <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
            亚洲乱码日产精品a级毛片久久 | 国产精品久久久久jk制服| 久久天天躁狠狠躁夜夜躁2014| 亚洲精品乱码久久久久久| 久久噜噜电影你懂的| 亚洲欧美国产精品专区久久| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 国产激情久久久久影院老熟女免费| 亚洲精品乱码久久久久久蜜桃 | 精品久久久无码21p发布| 国产亚洲综合久久系列| 亚洲国产日韩欧美综合久久| …久久精品99久久香蕉国产 | 亚洲国产精品一区二区久久| 久久人妻无码中文字幕| 一本色道久久88加勒比—综合| 女人高潮久久久叫人喷水| 久久精品国内一区二区三区| 国产A级毛片久久久精品毛片| 女人香蕉久久**毛片精品| 99久久精品免费看国产一区二区三区| 亚洲嫩草影院久久精品| 久久精品国产亚洲AV无码娇色 | 久久久午夜精品福利内容| 久久久久无码中| 日本福利片国产午夜久久| 久久A级毛片免费观看| 久久婷婷五月综合色高清| 性色欲网站人妻丰满中文久久不卡| 香蕉99久久国产综合精品宅男自 | 久久综合亚洲欧美成人| 欧美牲交A欧牲交aⅴ久久| 伊人久久精品无码av一区| 狠狠色狠狠色综合久久| 亚洲伊人久久精品影院| 亚洲AV成人无码久久精品老人| 久久人做人爽一区二区三区 | 精品无码久久久久久久动漫| 久久播电影网| 久久亚洲AV成人无码软件| 精品久久人人爽天天玩人人妻|