Notez qu'il était nécessaire à ABC156-D.
https://atcoder.jp/contests/abc156/tasks/abc156_d
nC_k = \frac{n!}{(n-k)!k!}
La définition de $ nC_k $ est ↑, donc si vous écrivez ceci tel qu'il est dans le code,
import math
def comb(n,k):
math.factorial(n) // (math.factorial(n - k) * math.factorial(k))
print(comb(4,2))
# 6
Ça ressemble à ça. Cependant, $ n! $ Est $ O (n) $, donc dans le cas de $ n \ leqq10 ^ 9 $ comme ABC156-D cette fois, le temps de calcul sera long et il ne sera pas dans le temps. Je dois en quelque sorte raccourcir le temps de calcul.
Vous devez d'abord connaître la méthode des carrés itératifs et le théorème de Fermat.
Comment trouver la puissance de la puissance à grande vitesse.
En python, vous pouvez calculer le reste en divisant $ x ^ n $ par $ mod $ en utilisant pow (x, n, mod).
Lorsque $ p $ est un nombre premier et $ a $ est un entier qui n'est pas un multiple de $ p $ ($ a $ et $ p $ sont des nombres premiers l'un de l'autre), ce qui suit est vrai.
a^{p-1} \equiv 1 (mod\, p)
Le fait est que si vous divisez $ a ^ {p-1} $ par $ p $, c'est trop.
$ nC_k $ peut être transformé comme suit.
nC_k = \frac{n!}{(n-k)!k!}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}
Faites maintenant attention à $ \ frac {1} {k!} $.
Du théorème de Fermat
a^{p-1} mod\, p = 1 \\ \\
a^{p-2} mod\, p = \frac{1}{a} \\
Vous obtenez $ a ^ {p-2} mod , p = \ frac {1} {a} $. Par conséquent, $ \ frac {1} {k!} = K! ^ {P-2} mod , p $ tient, et $ k! ^ {P-2} $ peuvent être calculés à grande vitesse par la méthode itérative du carré. , $ \ Frac {1} {k!} $ Peut être calculé à grande vitesse.
D'après ce qui précède, $ nC_k $ peut être exprimé comme suit.
nC_k = n(n-1)\cdots(n-k+1) \times(k!^{p-2}\,mod\,p)
Le montant du calcul est de O $ (k)
# O(k)
def comb(n,k):
nCk = 1
MOD = 10**9+7
for i in range(n-k+1, n+1):
nCk *= i
nCk %= MOD
for i in range(1,k+1):
nCk *= pow(i,MOD-2,MOD)
nCk %= MOD
return nCk
print(comb(4,2))
# 6
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86 https://note.com/tanon_cp/n/ncff944647054
Recommended Posts