二项式系数modulo 142857

Question

如何计算大n和和的二项式系数模数142857 r.142857有什么特别之处吗？如果问题是模数p在哪里p是素数那么我们可以使用卢卡斯定理但是应该为142857做什么.

Answer 1

算法是:

• 将基数分解为主要权力; 142857 = 3 ^ 3×11×13×37
• 计算结果模数每个主要权力
• 使用中国剩余定理结合结果.

要计算(n above k) mod p^q:

资料来源:http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf,定理1

定义(n!)_p为1..n不可分辨的数字的乘积p

在删除基数中的最低有效数字后定义n_j为njp

定义r为n-k

定义e_j为添加时k+r的进j位数,不计算来自最低位的进位数,以基数计算p

定义s为1如果p=2 & q>=3和-1否则

然后(n above k) mod p^q := p^e_0 * s^e_(q-1) * concatenate(j=d..0)( (n_j!)_p / ((k_j!)_p*(r_j!)_p) ),在连接的每个项计算结果的一个基数p,最低j计算最不重要的非零数字.

Answer 2

实际上,你可以计算出C(n,k) % m在O(n)时间任意m.

诀窍是计算n!,k!并(n-k)!作为素数幂矢量,从第一个中减去两个,然后将余数乘以模数m.对于C(10, 4)我们这样做:

10! = 2^8 * 3^4 * 5^2 * 7^1
 4! = 2^3 * 3^1
 6! = 2^4 * 3^2 * 5^1

于是

C(10,4) = 2^1 * 3^1 * 5^1 * 7^1

我们可以很容易地计算出来,mod m因为没有分歧.诀窍是n!在线性时间内计算和朋友的分解.如果我们预先计算质数n,我们可以如下有效地做到这一点:显然,对于产品中的每个偶数,1*2*...*9*10我们得到一个因子2.对于每个第四个数字,我们得到第二个,依此类推.因此,2因素的数量n!是n/2 + n/4 + n/8 + ...(在哪里/是地板).我们对剩余的素数做同样的事情,并且由于O(n/logn)素数小于n,而且我们确实O(logn)为每个素数工作,因此分解是线性的.

在实践中,我会更加隐含如下编码:

func Binom(n, k, mod int) int {
    coef := 1
    sieve := make([]bool, n+1)
    for p := 2; p <= n; p++ {
        if !sieve[p] {
            // Sieve of Eratosthenes
            for i := p*p; i <= n; i += p {
                sieve[i] = true
            }
            // Calculate influence of p on coef
            for pow := p; pow <= n; pow *= p {
                cnt := n/pow - k/pow - (n-k)/pow
                for j := 0; j < cnt; j++ {
                    coef *= p
                    coef %= mod
                }
            }
        }
    }
    return coef
}

这包括一个Eratosthenes的筛子,所以运行时间nloglogn不是n如果预先计算或用更快的筛子筛分.