Es ist eine inverse Restoperation, die häufig in der Wettbewerbsprogrammierung verwendet wird, aber es scheint, dass sie mit der in Python 3.8 oder höher integrierten Funktion pow berechnet werden kann.
Bisher war es erforderlich, eine eigene Funktion zu erstellen, um den Rest des inversen Elements anhand der im folgenden Artikel beschriebenen Methode zu ermitteln. Eine Besonderheit, wie man "zu viel geteilt durch 1000000007" findet! ~ Vom inversen Element zum diskreten Logarithmus ~ (Qiita)
Zum Beispiel in Python 3.8 oder höher
38^{-1}\,\,mod\,\,97
Wenn Sie berechnen möchten
pow(38, -1, 97)
Sie können mit berechnen.
Python3.7 Integrierte Funktionen-pow (x, y [, z])
pow(x, y[, z]) Gibt die y-te Potenz von x zurück. Wenn z existiert, wird der Rest von z für die y-te Potenz von x zurückgegeben ~ Ausgelassen ~ Wenn es> z gibt, müssen x und y vom ganzzahligen Typ sein und y darf nicht negativ sein.
Python3.8 Eingebaute Funktionen-pow (base, exp [, mod])
pow(base, exp[, mod]) Gibt die Expth-Potenz der Basis zurück. Wenn es einen Mod gibt, wird der Rest des Mods für die Expth-Potenz der Basis zurückgegeben ~ Ausgelassen ~ For int operands base and exp, if mod is present, mod must also be of integer type and mod must be nonzero. If mod is present and exp is negative, base must be relatively prime to mod. In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.
Die 3.7-Dokumentation besagt, dass das Argument "pow (x, y, z)" y "(" exp ") nicht negativ sein darf, wenn es ein Argument" z "(" mod ") gibt. Diese Beschreibung wurde in der 3.8-Dokumentation entfernt. Die 3.8-Dokumentation besagt, dass, wenn das Argument "pow (base, exp, mod)" exp "eine negative Zahl ist, die" base "und" mod "zueinander prim sein müssen und das Argument" exp " Ermöglicht negative Zahlen auch mit mod`.
keigo0205@MacBook-Pro ~ % python --version
Python 3.8.2
keigo0205@MacBook-Pro ~ % python
Python 3.8.2 (default, Mar 24 2020, 11:35:26)
[Clang 11.0.0 (clang-1100.0.33.17)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(38, -1, 97)
23
>>> 23 * 38 % 97 == 1
True
>>> exit()
keigo0205@MacBook-Pro ~ % python --version
Python 3.7.7
keigo0205@MacBook-Pro ~ % python
Python 3.7.7 (default, Mar 24 2020, 13:42:02)
[Clang 11.0.0 (clang-1100.0.33.17)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(38, -1, 97)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: pow() 2nd argument cannot be negative when 3rd argument specified
>>> exit()
Korrekt···
Lösen wir ABC159-D --Bouquet. AtCoders Python ist Version 3.8.2.
Problemzusammenfassung Angesichts der natürlichen Zahlen "n" und der verschiedenen natürlichen Zahlen "a" und "b" darunter. Finden Sie die Antwort der folgenden Formel geteilt durch "10 ** 9 + 7". Beachten Sie jedoch, dass "a" und "b" kleiner oder gleich "2 * 10 ** 5" sind.
2^n - 1 - nCa - nCb
n, a, b = list(map(int, input().split()))
MOD = 10**9 + 7
# 1!Ab max(a, b)!Das umgekehrte Element bis wird durch MOD geteilt
#n bis n-max(a*b)Teilen Sie durch MOD, um den Rest zu finden.
fact = {}
fact[n] = n
fact[n - 1] = fact[n] * (n - 1) % MOD
inv_fact = [0] * (max(a, b) + 1)
inv_fact[1] = 1
for i in range(2, max(a, b) + 1):
fact[n - i] = fact[n - i + 1] * (n - i) % MOD
inv_fact[i] = inv_fact[i - 1] * pow(i, -1, MOD) % MOD
subtrahend = 1 + fact[n - a + 1] * inv_fact[a] + fact[n - b + 1] * inv_fact[b]
minuend = pow(2, n, MOD)
print((minuend + 2 * MOD - subtrahend) % MOD)
Ich habe es eingeführt, weil die Funktion der integrierten Funktion in Python 3.8 erweitert wurde. Sie sollten die offizielle Dokumentation regelmäßig lesen.
Persönlich bin ich froh, einfach den Reverse Mod schreiben zu können, ohne meine eigene Funktion mitbringen zu müssen.
Recommended Posts