Comment puis-je trouver mod de grand C (n, r)

Question

Comment puis-je trouver C (n, r) mod k où

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

J'ai trouvé des liens pour résoudre ce en utilisant Lucas theoremhere.

Mais cela ne m'aiderait pas dans les cas où mes n, r, K sont tous grands. L'extension de ce problème est le suivant: -

somme Trouver des séries comme: -

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

contraintes d'origine tiennent.

Merci.

Answer 1

Je sais algorithme avec complexité O (r * de log_n) chercher d'abord à l'algorithme à calco C (n, r) sans mod k:

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

Dans votre cas, vous ne pouvez pas diviser, parce que vous utilisez l'arithmétique modulaire. Mais vous pouvez multiplier sur l'élément modulaire multiplicatif inverse, des informations à ce sujet vous pouvez trouver ici https://en.wikipedia.org/wiki/Modular_multiplicative_inverse. code Vous sera comme ceci:

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

Answer 2

Ceci est un cas d'utilisation typique pour la programmation dynamique. Le triangle de Pascal nous donne

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

Nous savons aussi

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

Vous pouvez appliquer le module à chacun des sous-résultats pour éviter tout débordement. Le temps et la complexité de la mémoire sont tous les deux O (n^2)

Answer 3

Je pense que le moyen le plus rapide sera d'utiliser l'inverse modulaire.

La complexité sera aussi faible que log(n)

par exemple

ncr(x, y) % m sera

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

maintenant si vous avez besoin de calculer (a/b) % m que vous pouvez faire (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!

Comme k est un nombre premier, pour chaque r < k nous pouvons trouver sa inverse multiplicatif modulairer^-1 en utilisant l'algorithme d'Euclide étendu à O(lg n). Par conséquent, vous pouvez calculer ((n-r+1)!/r) % k en tant que (((n-r+1)! % k) * r^-1) % k. Faites-le sur 1~r alors vous obtiendrez le résultat.