Hızlı n Büyük n için k mod p seçimini yapın?

Question

"Büyük n" ile kastediyorum milyonlarca şeydir. p asaldır.

Ben http://apps.topcoder.com/wiki/display/tc/SRM+467 denedim ama işlevi yanlış gibi görünüyor

denedim http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 (ı 144 6 mod 5 seçim ve bana 2 vermelidir zaman bana 0 verir ile test) Ama ben tam anlamıyorum

Ayrıca mantığı (n-1, k-1, p)% p + kombinasyonları (n-1, k, birleşimlerini kullanan bir yinelemeli yinelemeli işlev yaptım. p)% p) ​​fakat n bana büyük taşma problemleri veriyor çünkü n büyük

Lucas Theorem'i denedim ama ya yavaş ya da yanlış görünüyor.

Tüm yapmaya çalıştığım, büyük n için hızlı/doğru n seçim k mod p oluşturmaktır. Herkes bana bunun için iyi bir uygulama olduğunu gösterebilirse çok minnettar olurum. Teşekkürler. Burada, Yani

std::map<std::pair<long long, long long>, long long> memo; 

long long combinations(long long n, long long k, long long p){ 
    if (n < k) return 0; 
    if (0 == n) return 0; 
    if (0 == k) return 1; 
    if (n == k) return 1; 
    if (1 == k) return n; 

    map<std::pair<long long, long long>, long long>::iterator it; 

    if((it = memo.find(std::make_pair(n, k))) != memo.end()) { 
     return it->second; 
    } 
    else 
    { 
     long long value = (combinations(n-1, k-1,p)%p + combinations(n-1, k,p)%p)%p; 
     memo.insert(std::make_pair(std::make_pair(n, k), value)); 
     return value; 
    } 
} 

Answer 1

sorununuzu çözebilir nasıl: istenen gibi

, yığın vurur memoized versiyonu büyük n için taşıyor. p karşılıklı asal olduğu gibi, Şimdi

long long res = 1; 
for (long long i = n; i > n- k; --i) { 
    res = (res * i) % p; 
} 

:

comb(n,k) = n!/(k!*(n-k)!) = (n*(n-1)*...(n-k+1))/k! 

(http://en.wikipedia.org/wiki/Binomial_coefficient#Computing_the_value_of_binomial_coefficients bakınız)

Sen payın hesaplamak için biliyorum: Elbette

formülünü biliyor p ile coprime olan her tamsayı iyi tanımlanmış yani ^-1 fo olabilir und. Bu Fermat teoremini bir ^p-1 = 1 (mod p) => a * ^p-2 = 1 (mod p) ve böylece ^-1 bir ^p-2 = kullanılarak yapılabilir . Şimdi tüm yapmanız gereken (örneğin ikili yöntemini kullanarak) hızlı üs uygulamaktır:

long long degree(long long a, long long k, long long p) { 
    long long res = 1; 
    long long cur = a; 

    while (k) { 
    if (k % 2) { 
     res = (res * cur) % p; 
    } 
    k /= 2; 
    cur = (cur * cur) % p; 
    } 
    return res; 
} 

Şimdi de bizim sonuca payda ekleyebilirsiniz:

long long res = 1; 
for (long long i = 1; i <= k; ++i) { 
    res = (res * degree(i, p- 2)) % p; 
} 

Ben unutmayın tür taşmasını önlemek için her yerde uzun süre kullanıyor. Tabii ki k üs alma yapmak gerekmez - Eğer k (mod p) hesaplanması ve daha sonra sadece bir kez bölebilirsiniz:

long long denom = 1; 
for (long long i = 1; i <= k; ++i) { 
    denom = (denom * i) % p; 
} 
res = (res * degree(denom, p- 2)) % p; 

EDIT: k> = p k eğer @ dbaupp yorumuna göre! 0 modulo p'ye eşit olacak ve (k!)^- 1 tanımlanmayacaktır. İlk önce, n'nin n * (n-1) ... (n-k + 1) ve k'de olduğu dereceyi hesaplamaktan kaçının. ve bunları karşılaştırmak:

int get_degree(long long n, long long p) { // returns the degree with which p is in n! 
    int degree_num = 0; 
    long long u = p; 
    long long temp = n; 

    while (u <= temp) { 
    degree_num += temp/u; 
    u *= p; 
    } 
    return degree_num; 
} 

long long combinations(int n, int k, long long p) { 
    int num_degree = get_degree(n, p) - get_degree(n - k, p); 
    int den_degree = get_degree(k, p); 

    if (num_degree > den_degree) { 
    return 0; 
    } 
    long long res = 1; 
    for (long long i = n; i > n - k; --i) { 
    long long ti = i; 
    while(ti % p == 0) { 
     ti /= p; 
    } 
    res = (res * ti) % p; 
    } 
    for (long long i = 1; i <= k; ++i) { 
    long long ti = i; 
    while(ti % p == 0) { 
     ti /= p; 
    } 
    res = (res * degree(ti, p-2, p)) % p; 
    } 
    return res; 
} 

EDIT: Yukarıdaki çözüm eklenebilir bir daha optimizasyon yok - yerine k her çoklu ters numarasını hesaplama !, biz k hesaplayabilir!(mod p) ve sonra bu sayının tersini hesaplar. Bu nedenle, üstelleşme için logaritmayı sadece bir kez ödemek zorundayız. Elbette yine, her bir çoğunun p bölücülerini atmak zorundayız. Büyük k için

long long denom = 1; 
for (long long i = 1; i <= k; ++i) { 
    long long ti = i; 
    while(ti % p == 0) { 
    ti /= p; 
    } 
    denom = (denom * ti) % p; 
} 
res = (res * degree(denom, p-2, p)) % p; 

Answer 2

iki temel gerçekleri istismar ederek çalışmalarını önemli ölçüde azaltabilir: Biz sadece bu son döngü değiştirmek zorunda p asal, üs ise

1. n!'un ana faktörü olarak p, s_p(n) tarafından p temsili (p = 2, bu popcount için) gösterimde s_p(n) göstergesinin toplamıdır. Dolayısıyla, choose(n,k)'un ana faktörizasyonunda p'un üssü, olup, özellikle k + (n-k) ilavesinin, p bazında gerçekleştirildiği zaman taşınmaması durumunda sıfırdır (üs, taşıma sayısıdır).

2. Wilson'un teoremi

   :p ancak ve ancak (p-1)! ≡ (-1) (mod p) bile, bir asal olduğunu.

n! ait factorisation içinde p üs genellikle

long long factorial_exponent(long long n, long long p) 
{ 
    long long ex = 0; 
    do 
    { 
     n /= p; 
     ex += n; 
    }while(n > 0); 
    return ex; 
} 

p tarafından choose(n,k) ait bölünebilme onay kesinlikle gerekli olmadığı hesaplanır, ancak bunun beri, öncelikle bu olması mantıklı olduğunu genellikle olacak ve daha az iş olacak:

long long choose_mod(long long n, long long k, long long p) 
{ 
    // We deal with the trivial cases first 
    if (k < 0 || n < k) return 0; 
    if (k == 0 || k == n) return 1; 
    // Now check whether choose(n,k) is divisible by p 
    if (factorial_exponent(n) > factorial_exponent(k) + factorial_exponent(n-k)) return 0; 
    // If it's not divisible, do the generic work 
    return choose_mod_one(n,k,p); 
} 

Şimdi daha yakın n! numaralı telefondan. ≤ n numaralarını p'un katları vearasındaki coprime sayılarına ayırırız.

n = q*p + r, 0 ≤ r < p 

ile p katları p^q * q! katkıda bulunur. p numaralı rakamlar, 0 ≤ j < q için (j*p + k), 1 ≤ k < p ürününe ve (q*p + k), 1 ≤ k ≤ r ürününe katkıda bulunur.

Sayılarla ilgili olarak p numaralı kurabiyeler için p katkısı ile ilgileneceğiz. j*p + k, 1 ≤ k < p tam çalışmalarının her biri (p-1)! modulo p ile uyumludur, dolayısıyla hepsi (-1)^q modulo p'un bir katkısını üretirler. Son (muhtemelen) tamamlanmamış çalışma, r! modulo p üretir.

yüzden

n = a*p + A 
k = b*p + B 
n-k = c*p + C 

biz cop(m,r) tüm sayıların ürün ≤ m*p + r olan p için aralarında asal olduğu

choose(n,k) = p^a * a!/ (p^b * b! * p^c * c!) * cop(a,A)/(cop(b,B) * cop(c,C)) 

olsun yazarsanız.

İki olasılık vardır, a = b + c ve A = B + C veya a = b + c + 1 ve A = B + C - p. Hesaplamada, ikinci olasılığı önceden elimine ettik, fakat bu gerekli değildir. choose(a,b) gelen İlk durumda

, p açık güçler iptal ve biz

choose(n,k) = a!/(b! * c!) * cop(a,A)/(cop(b,B) * cop(c,C)) 
      = choose(a,b) * cop(a,A)/(cop(b,B) * cop(c,C)) 

ile choose(n,k) bölen p Herhangi yetkilerini bırakılır - bizim durumumuzda, orada yok olacak, biz yapmaya başladığımdan beri önce bu durumları ortadan ettik - cop(a,A)/(cop(b,B) * cop(c,C)) bir tamsayı olması gerekmez, ancak ve (-1) iptal ifade modulo p dikkate alındığında, cop(m,r)a = b + c beri (-1)^m * r! için azaltır, böylece (örneğin choose(19,9) (mod 5) düşünün) ve bizkalır İkinci durumda

choose(n,k) ≡ choose(a,b) * choose(A,B) (mod p) 

, biz a = b + c + 1 beri

choose(n,k) = choose(a,b) * p * cop(a,A)/ (cop(b,B) * cop(c,C)) 

bulabilirsiniz. son hanede bir taşıma, böylece payıdır anlamı, biz modüler ters tarafından bir çarpma ile bölünme yerini alacak şekilde kullanılabilir burada (p

p * cop(a,A)/(cop(b,B) * cop(c,C)) ≡ 0 = choose(A,B) 

modülo veya rasyonel bir sayı bağdaşım olarak görüntülemek A < B demektir p tarafından bölünebilir. Neyse, biz yine

choose(n,k) ≡ choose(a,b) * choose(A,B) (mod p) 

Şimdi choose(a,b) bölümü için tekrarlayabilir bulabilirsiniz.

Örnek:

choose(144,6) (mod 5) 
144 = 28 * 5 + 4 
    6 = 1 * 5 + 1 
choose(144,6) ≡ choose(28,1) * choose(4,1) (mod 5) 
       ≡ choose(3,1) * choose(4,1) (mod 5) 
       ≡ 3 * 4 = 12 ≡ 2 (mod 5) 

choose(12349,789) ≡ choose(2469,157) * choose(4,4) 
        ≡ choose(493,31) * choose(4,2) * choose(4,4 
        ≡ choose(98,6) * choose(3,1) * choose(4,2) * choose(4,4) 
        ≡ choose(19,1) * choose(3,1) * choose(3,1) * choose(4,2) * choose(4,4) 
        ≡ 4 * 3 * 3 * 1 * 1 = 36 ≡ 1 (mod 5) 

Şimdi uygulaması:

// Preconditions: 0 <= k <= n; p > 1 prime 
long long choose_mod_one(long long n, long long k, long long p) 
{ 
    // For small k, no recursion is necessary 
    if (k < p) return choose_mod_two(n,k,p); 
    long long q_n, r_n, q_k, r_k, choose; 
    q_n = n/p; 
    r_n = n % p; 
    q_k = k/p; 
    r_k = k % p; 
    choose = choose_mod_two(r_n, r_k, p); 
    // If the exponent of p in choose(n,k) isn't determined to be 0 
    // before the calculation gets serious, short-cut here: 
    /* if (choose == 0) return 0; */ 
    choose *= choose_mod_one(q_n, q_k, p); 
    return choose % p; 
} 

// Preconditions: 0 <= k <= min(n,p-1); p > 1 prime 
long long choose_mod_two(long long n, long long k, long long p) 
{ 
    // reduce n modulo p 
    n %= p; 
    // Trivial checks 
    if (n < k) return 0; 
    if (k == 0 || k == n) return 1; 
    // Now 0 < k < n, save a bit of work if k > n/2 
    if (k > n/2) k = n-k; 
    // calculate numerator and denominator modulo p 
    long long num = n, den = 1; 
    for(n = n-1; k > 1; --n, --k) 
    { 
     num = (num * n) % p; 
     den = (den * k) % p; 
    } 
    // Invert denominator modulo p 
    den = invert_mod(den,p); 
    return (num * den) % p; 
} 

modüler tersini hesaplamak için kullanabileceğiniz Fermat (sözde küçük) teoremi

ise p asal ve a bölünemez değil b y p, daha sonra a^(p-1) ≡ 1 (mod p).

ve a^(p-2) (mod p) olarak tersini hesaplamak ya da sen göreceli asal (pozitif) herhangi bir tamsayı çifti için modüler ters elde bağımsız değişkenler daha geniş bir aralığı genişletilmiş Öklid algoritması ya devam fraksiyonu genişleme için geçerli bir yöntemi kullanmak: a^(p-2) (mod p) hesaplama gibi

long long invert_mod(long long k, long long m) 
{ 
    if (m == 0) return (k == 1 || k == -1) ? k : 0; 
    if (m < 0) m = -m; 
    k %= m; 
    if (k < 0) k += m; 
    int neg = 1; 
    long long p1 = 1, p2 = 0, k1 = k, m1 = m, q, r, temp; 
    while(k1 > 0) { 
     q = m1/k1; 
     r = m1 % k1; 
     temp = q*p1 + p2; 
     p2 = p1; 
     p1 = temp; 
     m1 = k1; 
     k1 = r; 
     neg = !neg; 
    } 
    return neg ? m - p2 : p2; 
} 

, bu bazı girişler için bu diğerleri için daha yavaş olduğunu, (bu oldukça hızlıdır küçük k ve büyük p için bu yüzden, aslında O(min(log k, log p)) var) önemli ölçüde daha hızlı olduğunu, bir O(log p) algoritmadır.

Genel olarak, binom katsayıları her binom katsayısı O (p * log_p k) olmak üzere toplam karmaşıklığını verimli, en O (p) işlemleri anda ihtiyacı p, modulo en O (log_p k) de hesaplamak gerekir bu şekilde operasyonları . k, p'dan önemli ölçüde daha büyük olduğunda, bu O(k) çözümden çok daha iyidir. k <= p için, bazı ek yükü olan O(k) çözümüne indirgenir.