Annahme

Es wurde benötigt, um ABC156 D Bouquet zu lösen. Der Zustand dieses Problems ist p = 10^{9}+7 2 \leq n \leq 10^{9} 1 \leq r \leq 2 \times 10^{5}

Später, als ich ABC167 E Colourful Blocks löste, fügte ich es hinzu, weil ich die erweiterte euklidische Methode der gegenseitigen Teilung verwendete.

Fazit

`Methode nach dem Satz von Fermat`


def ncr(n, r, mod):
    ret = 1
    for i in range(1, r+1):
        ret = (ret * (n-i+1) * pow(i, mod-2, mod)) % mod
    return ret

`Methode unter Verwendung der erweiterten euklidischen Methode der gegenseitigen Teilung`


def ncr_eu(n, r, mod):
    ret = 1
    if r < n:
        inv = [1]
        for i in range(1, r+1):
            inv.append(max(1, (-(mod//i) * inv[mod % i]) % mod))
            ret = ret*(n+1-i)*inv[i] % mod
    return ret

"Mod" ist jedoch eine Primzahl

Kommentar

Anzahl der Kombinationen

Die Kombination zur Auswahl von $ r $ aus $ n $

_n C _r = \frac{n!}{r!(n-r)!}

Also einfach

from math import factorial

def ncr(n, r):
    return factorial(n) // factorial(r) // factorial(n-r)

Ich möchte, aber es ist sehr langsam.

Satz von Fermat

Ich möchte $ x! \ Pmod {p} $ berechnen, um "Fakultät" für eine schnellere Berechnung zu ersetzen, aber einfach

_n C _r \equiv \frac{n!\bmod p}{(r!\bmod p)((n-r)!\bmod p)}\bmod p

Es scheint, dass es nicht sein wird. Deshalb spreche ich den Satz von Fermat an.

a^{p-1} \equiv 1 \bmod p

Wenn sich $ a $ und $ p $ gegenseitig ausschließen, können beide Seiten durch $ a $ geteilt werden.

a^{p-2} \equiv a^{-1} \bmod p

Wird erhalten. Es scheint, dass dieses $ a ^ {-1} $ das inverse Element (Gyakugen) genannt wird. Mit diesem

_n C _r \equiv (n!\bmod p)((r!)^{p-2}\bmod p)(((n-r)!)^{p-2}\bmod p) \bmod p

Und es kann nur durch Multiplikation ausgedrückt werden.

Wiederholte quadratische Methode

Um $ x ^ {p-2} $, das hier häufig verwendet wird, mit hoher Geschwindigkeit zu berechnen

\begin{eqnarray}
x^{2} &=& x \cdot x \\
x^{4} &=& x^{2} \cdot x^{2} \\
x^{8} &=& x^{4} \cdot x^{4} \\
\cdots
\end{eqnarray}

Es ist eine Technik, um den Rechenaufwand zu reduzieren, aber in Python ist es schneller, das Standard-Pow zu verwenden.

Implementierungsbeispiel

def bpow(x, y, z):
    a = 1
    while y:
        if y & 1:
            a = (a*x) % z
        x = (x*x) % z
        y >>= 1
    return a

Erweiterte euklidische gegenseitige Teilung

Obwohl es als euklidische Methode der gegenseitigen Teilung bezeichnet wird, ist es für eine intuitivere Methode erforderlich. Sei $ q $ der Quotient aus $ p $ geteilt durch $ a $ und $ r $ der Rest.

\begin{eqnarray}
p &=& qa+r \\
0 &\equiv& qa + r \bmod p \\
0 &\equiv& q + a^{-1} r \bmod p \\
a^{-1} &\equiv& -q \cdot r^{-1} \bmod p \\
\end{eqnarray}

Da das inverse Element von $ a $ unter Verwendung des inversen Elements des Intervalls $ [1, a) $ berechnet wird, ist es effizient, wenn $ n $ von $ _n C _r $ fest ist und mehrere $ r $ erforderlich sind. ..

Referenz: [So finden Sie den häufig verwendeten Binomialkoeffizienten (nCk mod. P) und das inverse Element (a ^ -1 mod. P) --Kenchons professioneller Andachtsrekord](https://drken1215.hatenablog.com/entry / 2018/06/08/210000)

[Python] nCr mod Primzahlen berechnen