Beachten Sie, dass ABC156 D --Bouquet nicht gelöst werden konnte, ohne die Verarbeitung des Titels zu kennen.
\sum_{r=0}^{n}{}_{n}{\rm C}_{r}=2^{n}
Binärsatz $ (a + b) ^ n = \ sum_ {r = 0} ^ n {} _n \ mathrm {C} _ra ^ {n-r} b ^ {r} $
(1+1)^{n} = \sum_{r=0}^n{}_n\mathrm{C}_r1^{n-r}1^{r} = \sum_{r=0}^{n}{}_{n}{\rm C}_{r}
∴2^{n} = \sum_{r=0}^{n}{}_{n}{\rm C}_{r}
Der Artikel, auf den ich mich bezog. Die Bedeutung des Binomialsatzes und zweier Beweise
Die korrekte Berechnung des Binomialkoeffizienten nimmt viel Zeit in Anspruch. Versuchen wir, den Binomialkoeffizienten mit der Fakultät des Mathematikmoduls unter den Bedingungen von n = 10 ^ 6 und r = 1000 zu berechnen.
import math
import time
import numpy as np
n=1000000
r=1000
sta = time.time()
ans = np.power(2,n)-1
end1 = time.time()
print("Sollte Zeit fahren:",sta-end1)
ab = math.factorial(n)//(math.factorial(r)*math.factorial(n-r)) #Weil der Schwimmer überläuft/Ist nicht möglich
end2 = time.time()
print("Binäre Berechnungszeit:",end2-end1)
·Ergebnis Einschaltdauer: 0,0 Sek Binäre Berechnungszeit: 14.03599739074707 Sek
Im Wettbewerb Pro ist n = 10 ^ 9 rau, also wird es TLE sein, wie es ist.
Artikel, auf die verwiesen wird Zusammenfassung zur Berechnung der Berechnungsbetrag! ~ Woher kommt das Protokoll ~
In den meisten Fällen kann der berechnete Wert des Binomialkoeffizienten selbst nicht erhalten werden, der Rest jedoch durch Teilen des Binomialkoeffizienten durch 10 ^ 9 + 7. In diesem Fall gibt es eine Methode zur schnellen Berechnung, die durch das folgende Verfahren realisiert wird.
① Berechnen Sie mod (10 ^ 9 + 7) für jeden Term von nCr vor
{}_{n}{\rm C}_{r} = \frac{n!}{r!(n-r)!} = (n!)(r!)^{-1}((n-r)!)^{-1}
Von $ (n!) $, $ (R!) ^ {-1} $, $ ((nr)!) ^ {-1} $, geteilt durch mod (10 ^ 9 + 7) Berechnen Sie den Rest im Voraus.
② Multiplizieren Sie die vorberechneten Terme
calc_mod.py
import time
#① Mod jedes Elements von nCr(10^9+7)Vorberechnet
p = 10 ** 9 + 7
N = 10 ** 7 #Bereiten Sie so viel N vor, wie Sie benötigen
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1] #Faktinv zur Berechnung
for i in range(2, N + 1):
fact.append((fact[-1] * i) % p)
inv.append((-inv[p % i] * (p // i)) % p)
factinv.append((factinv[-1] * inv[-1]) % p)
#② Multiplizieren Sie die vorberechneten Terme
def cmb(n, r, p):
if (r < 0) or (n < r):
return 0
r = min(r, n - r)
return fact[n] * factinv[r] * factinv[n-r] % p
start = time.time()
n = 10**6
r = 10**4
print(cmb(n, r, p))
# 667918653
end = time.time()
print('{} sec'.format(end-start))
# 0.0 sec
Artikel, auf die verwiesen wird Ich möchte den Binomialkoeffizienten nCr mit Python mit hoher Geschwindigkeit berechnen Modulmathematik Quadratische Methode wiederholen [[So finden Sie nCr mod m]] Grundlagen der kryptografischen Theorie ab invmod Verständnis der modularen Inversen, die zur Berechnung von 3 ÷ 4 ≡ 9 mod 11 erforderlich sind
Soweit ich das beurteilen kann, gibt es in Python fünf Möglichkeiten, Power zu machen. Ich war neugierig, welches das schnellste war, also habe ich nachgeforscht.
Die Erhebungsmethode verglich die Berechnungsgeschwindigkeit von 10 ^ 9 von 2.
import time
import math
import numpy as np
x = 2
n = 10**9
#Selbstdefinierte iterative Quadratmethode
def self_pow(x, n):
ans = 1
while(n > 0):
if n%2 == 1:
ans *= x
x *= x
n = n >> 1
return ans
start = time.time()
#Wenn Sie Ihre eigene iterative Quadratmethode verwenden
ans1 = self_pow(x,n)
end1 = time.time()
self_pow_time1 = end1 - start
print ("time1: {0}".format(self_pow_time1) + "[sec]")
#Die Kraft, die eingebaut werden soll
ans2 = x**n
end2 = time.time()
beki_time2 = end2 - end1
print ("time2: {0}".format(beki_time2) + "[sec]")
#Eingebaute Leistung
ans3 = pow(x,n)
end3 = time.time()
pow_time3 = end3 - end2
print ("time3: {0}".format(pow_time3) + "[sec]")
#numpy.power
#Da es normalerweise als 32-Bit-Ganzzahl berechnet wird
ans4 = np.power(x,n)
end4 = time.time()
np_pow_time4 = end4 - end3
print ("time4: {0}".format(np_pow_time4) + "[sec]")
print(ans4)
#math.pow
ans5 = math.pow(x,n)
end5 = time.time()
math_pow_time5 = end5 - end4
print ("time5: {0}".format(math_pow_time5) + "[sec]")
·Ergebnis time1: 7.2481536865234375[sec] time2: 5.379794359207153[sec] time3: 5.220895767211914[sec] time4: ~~ 0.0 [sec] ~~ Überlauf und nicht richtig berechnet, Ausgabe inf Überlauffehler: Mathematikbereichsfehler für math.pow
Fazit: ~~ numpy.power ist die schnellste. ~~ Die eingebaute Leistung scheint etwas schneller zu sein. Meine eigene Funktion ist langsam, weil ich während benutze.
__2020 / 03/11 postscript __ In dem Kommentar haben Sie darauf hingewiesen, dass np.power nicht richtig berechnet werden konnte. Vielen Dank, dass Sie @mui_nyan. Es wurde auch auf der offiziellen Seite geschrieben. Es tut mir Leid. Scipy.org
np_power.py
x=2
n=10**9
print('normal:',np.power(x,n))
print('int64:',np.power(x,n, dtype=np.int64))
print('float64:',np.power(x,n, dtype=np.float64))
#normal: 0
#int64: 0
#float64: inf
Bitte beachten Sie, dass auch bei Überlauf kein Fehler auftritt.
pow.py
def mpow(a,n,mod):
if n == 0:
return 1
elif n == 1:
return a
elif n%2==0:
return (pow(a,n//2,mod))**2%mod
else:
return a*pow(a,n-1,mod)%mod
Die Bedeutung des Binomialsatzes und zweier Beweise Zusammenfassung zur Berechnung der Berechnungsbetrag! ~ Woher kommt das Protokoll ~ Ich möchte den Binomialkoeffizienten nCr mit Python mit hoher Geschwindigkeit berechnen Modulmathematik Quadratische Methode wiederholen [[So finden Sie nCr mod m]] Grundlagen der kryptografischen Theorie ab invmod Verständnis der modularen Inversen, die zur Berechnung von 3 ÷ 4 ≡ 9 mod 11 erforderlich sind Eine Besonderheit, wie man "zu viel geteilt durch 1000000007" findet! ~ Vom inversen Element zum diskreten Logarithmus ~
Recommended Posts