Wie kann ich mod großen C finden (n, r)

Question

Wie finde ich C (n, r) mod k wo

0 < n,r < 10^5 
k = 10^9 + 7 (large prime number) 

I Links gefunden habe, dies mit Lucas theoremhere zu lösen.

Aber das würde mir nicht in Fällen helfen, wo meine n, r, K alle groß sind. Die Erweiterung dieses Problems ist: -

Finding Summe von Serien wie: -

(C(n,r) + C(n, r-2) + C(n, r-4) + ......) % k 

Original-Einschränkungen halten.

Danke.

Answer 1

Ich weiß Algorithmus mit Komplexität O (r * log_n) Zunächst bei Algorithmus aussehen berechnet C (n, r) ohne mod k:

int res = 1; 
for(int i=1; i<=r; i++){ 
    res*=(n+1-i); 
    res/=i; 
} 

In Ihrem Fall, Sie können sich nicht teilen, weil Sie verwenden modulare Arithmetik. Aber Sie können auf dem modularen multiplikativen inversen Element multiplizieren, Informationen darüber finden Sie hier https://en.wikipedia.org/wiki/Modular_multiplicative_inverse. Sie Code wird so aussehen:

int res = 1; 
for(int i=1; i<=r; i++){ 
    res*=(n+1-i); 
    res%=k; 
    res*=inverse(i,k); 
    res%=k; 
} 

Answer 2

Dies ist ein typischer Anwendungsfall für die dynamische Programmierung. Pascals Dreieck gibt uns

C(n, r) = C(n-1, r) + C(n-1, r-1) 

Auch wissen wir

C(n, n) = 1 
C(n, 0) = 1 
C(n, 1) = n 

Sie können Modul zu jedem der Teilergebnisse gelten Überlauf zu vermeiden. Zeit und Speicher Komplexität sind beide O (n^2)

Answer 3

Ich denke, der schnellere Weg wird modulare Inverse verwenden.

Komplexität wird so niedrig wie log(n)

zum Beispiel

ncr(x, y) % m

a = fac(x) % m; 
b = fac(y) % m; 
c = fac(x-y) % m; 

jetzt sein, wenn Sie (a/b) % m berechnen müssen, können Sie tun (a % m) * (pow(b , m - 2) % m) // Using Fermat’s Little Theorem

https://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/

Answer 4

C(n,r) = n!/(r!(n-r)!) = (n-r+1)!/r!

Als k ist ein gutes, für jeden r < k wir seine modulare multiplikative Inverser^-1 Verwendung erweiterter euklidische Algorithmus in O(lg n) finden.

Sie können also ((n-r+1)!/r) % k als (((n-r+1)! % k) * r^-1) % k berechnen. Tun Sie es über 1~r dann erhalten Sie das Ergebnis.