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

            風(fēng)雨

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

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


            (轉(zhuǎn)載:http://acm.uva.es/board/viewtopic.php?f=22&t=42690&sid=25bd8f7f17abec626f2ee065fec3703b

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            久久久久久亚洲精品无码| 久久亚洲精品国产亚洲老地址| 久久久久久久久久久久久久| 2020国产成人久久精品| 久久99国产综合精品| 久久亚洲中文字幕精品一区| 国产成人无码精品久久久性色| 99久久中文字幕| 亚洲精品WWW久久久久久| 日本久久久久亚洲中字幕| 99久久99久久精品国产片果冻| 狠狠色丁香久久婷婷综合_中| 1000部精品久久久久久久久| 久久久久久久91精品免费观看| 九九99精品久久久久久| 亚洲精品tv久久久久久久久 | 一本久久a久久精品综合夜夜| 久久免费看黄a级毛片| 品成人欧美大片久久国产欧美| 日日躁夜夜躁狠狠久久AV| 中文字幕精品久久久久人妻| 伊人色综合久久天天| 狠狠色婷婷综合天天久久丁香 | 97久久国产亚洲精品超碰热| 亚洲国产成人精品无码久久久久久综合| 精品久久久久久中文字幕人妻最新| 久久婷婷色综合一区二区| 久久久久久久免费视频| 亚洲人AV永久一区二区三区久久| 精品久久久久久无码人妻热| 91久久精品91久久性色| 国内精品久久久久伊人av| 久久亚洲AV成人出白浆无码国产| 亚洲va中文字幕无码久久| 欧美噜噜久久久XXX| 国内精品伊人久久久久av一坑 | 久久亚洲精品无码观看不卡| 久久久久国产日韩精品网站| 久久久久国产一级毛片高清板| 欧洲国产伦久久久久久久| 久久亚洲中文字幕精品一区|