11

n大きなとの 142857 を法とする二項係数を計算する方法r。142857 について何か特別なことはありますか? 問題がモジュロpでどこpが素数であるかということであれば、ルーカスの定理を使用できますが、142857 に対してはどうすればよいでしょうか。

4

3 に答える 3

14

実際には任意C(n,k) % mの時間で計算できます。O(n)m

トリックは、 を計算しn!、素数べき乗ベクトルとして、最初の 2 つから後で 2 つを引き、余りを を法として掛けることです。これを行うため：k!(n-k)!mC(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。4 番目の数字ごとに、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した後に定義するnjp

次のように定義rしますn-k

e_jを加算するときのキャリーの数として定義し、最下位桁k+rからのキャリーをカウントせず、基数で計算しますjp

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 の 1 桁を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 に答える