11

如何计算大n和的二项式系数模 142857 r。142857有什么特别之处吗？如果问题是质数的模数p，p那么我们可以使用卢卡斯定理，但对于 142857 应该怎么做。

4

3 回答 3

14

您实际上可以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 p is not sieved yet, it is a prime number
        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
}

这包括一个埃拉托色尼筛，因此运行时间nloglogn不是n预先计算素数或用更快的筛子筛分的。

于 2014-06-30T23:25:44.973 回答
13

算法是：

  • 将基础分解为主要幂；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..np

定义n_j为n擦除j基数中的最低有效数字后p

定义r为n-k

定义e_j为添加时的进位数，k+r不计算从j最低位开始的进位，以基数计算p

定义s为1ifp=2 & q>=3和-1else

然后(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计算最低有效的非零数字。

于 2012-10-28T07:06:19.587 回答
3

142857 的特别之处在于 7 * 142857 = 999999 = 10^6 - 1。这是由费马小定理产生的一个因子，a=10 和 p=7，产生模等价 10^7 == 10（mod 7 ）。这意味着您可以在大多数情况下以 999999 为模数，并通过在最后除以 7 来减少最终模数。这样做的好处是，对于 k=1,2,3,6，模除法在 10^k 形式的表示基础中非常有效。在这种情况下，您所做的就是将数字组加在一起；这是淘汰九的概括。

只有当您有硬件以 10 为底的乘法时，这种优化才真正有意义。这真的是说，如果你必须用纸和铅笔来做这件事，它会很好用。由于这个问题最近出现在一个在线比赛中，我想这正是问题的由来。

于 2012-11-05T22:55:24.623 回答