Wenn Sie es ohne nachzudenken implementieren

nC_k = \frac{n!}{(n-k)!k!}

Die Definition von $ nC_k $ lautet ↑. Wenn Sie dies also so schreiben, wie es im Code steht,

import math
def comb(n,k):
    math.factorial(n) // (math.factorial(n - k) * math.factorial(k))

print(comb(4,2))
# 6

Es sieht aus wie das. $ N! $ Ist jedoch $ O (n) $. Im Fall von $ n \ leqq10 ^ 9 $ wie diesmal ABC156-D ist die Berechnungszeit also lang und nicht rechtzeitig. Ich muss die Rechenzeit irgendwie verkürzen.

Vorausgesetztes Wissen

Zuerst müssen Sie die iterative Quadratmethode und den Satz von Fermat kennen.

Wiederholte quadratische Methode

So finden Sie die Kraft der Kraft bei hoher Geschwindigkeit. In Python können Sie den Rest berechnen, indem Sie $ x ^ n $ durch $ mod $ dividieren, indem Sie "pow (x, n, mod)" verwenden.

Satz von Fermat

Wenn $ p $ eine Primzahl und $ a $ eine Ganzzahl ist, die kein Vielfaches von $ p $ ist ($ a $ und $ p $ sind Primzahlen voneinander), gilt Folgendes.

a^{p-1} \equiv 1 (mod\, p)

Der Punkt ist, dass wenn Sie $ a ^ {p-1} $ durch $ p $ teilen, es zu viel ist.

Transformiere nCk

$ nC_k $ kann wie folgt transformiert werden.

nC_k = \frac{n!}{(n-k)!k!}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}

Achten Sie nun auf $ \ frac {1} {k!} $.

Aus dem Satz von Fermat

a^{p-1} mod\, p = 1 \\ \\
a^{p-2} mod\, p = \frac{1}{a} \\

Sie erhalten $ a ^ {p-2} mod , p = \ frac {1} {a} $. Daher kann $ \ frac {1} {k!} = K! ^ {P-2} mod , p $ gilt und $ k! ^ {P-2} $ mit der iterativen Quadratmethode mit hoher Geschwindigkeit berechnet werden. , $ \ Frac {1} {k!} $ Kann mit hoher Geschwindigkeit berechnet werden.

Aus dem Obigen kann $ nC_k $ wie folgt ausgedrückt werden.

nC_k = n(n-1)\cdots(n-k+1) \times(k!^{p-2}\,mod\,p)

Der Berechnungsbetrag beträgt $ O (k) . ( K! $ Dauert am längsten)

Implementierung

# 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

Referenz

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

[Python] Wie man nCk ableitet (ABC156-D)