Notez que je n'ai pas pu résoudre le titre dans ABC156 D --Bouquet sans connaître le traitement du titre.
\sum_{r=0}^{n}{}_{n}{\rm C}_{r}=2^{n}
Théorème binaire $ (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}
L'article auquel j'ai fait référence. La signification du théorème binomial et deux preuves
Le calcul correct du coefficient binomial prend beaucoup de temps. Essayons de calculer le coefficient binomial avec factoriel du module mathématique dans les conditions de n = 10 ^ 6 et r = 1000.
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("Devrait monter le temps:",sta-end1)
ab = math.factorial(n)//(math.factorial(r)*math.factorial(n-r)) #Parce que le flotteur déborde/N'est pas possible
end2 = time.time()
print("Temps de calcul binaire:",end2-end1)
·résultat Temps de puissance: 0,0 sec Temps de calcul binaire: 14,03599739074707 sec
Dans la compétition pro, n = 10 ^ 9 est approximatif, donc ce sera TLE tel quel.
Articles référencés Résumé de la façon de calculer l'ordre de montant de calcul! ~ D'où vient le journal ~
Dans la plupart des cas, la valeur calculée du coefficient binomial lui-même ne peut pas être obtenue, mais le reste est obtenu en divisant le coefficient binomial par 10 ^ 9 + 7. Dans ce cas, il existe une méthode pour calculer rapidement, et elle est réalisée par la procédure suivante.
① Pré-calculer le mod (10 ^ 9 + 7) de chaque terme de nCr
{}_{n}{\rm C}_{r} = \frac{n!}{r!(n-r)!} = (n!)(r!)^{-1}((n-r)!)^{-1}
À partir de $ (n!) $, $ (R!) ^ {-1} $, $ ((nr)!) ^ {-1} $, divisé par mod (10 ^ 9 + 7) Calculez le reste à l'avance.
② Multipliez les termes pré-calculés
calc_mod.py
import time
#① mod de chaque élément de nCr(10^9+7)Pré-calculé
p = 10 ** 9 + 7
N = 10 ** 7 #Préparez autant de N que nécessaire
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1] #factinv pour le calcul
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)
#② Multipliez les termes pré-calculés
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
Articles référencés Je veux calculer le coefficient binomial nCr avec Python à grande vitesse Mathématiques du module Méthode de répétition du carré [[Comment trouver nCr mod m]]](https://ikatakos.com/pot/programming_algorithm/number_theory/mod_combination) Bases de la théorie cryptographique à partir d'invmod Comprendre les inverses modulaires nécessaires pour calculer 3 ÷ 4 ≡ 9 mod 11
Pour autant que je sache, il existe cinq façons de faire de la puissance en python. J'étais curieux de savoir lequel était le plus rapide, alors j'ai enquêté.
La méthode d'enquête a comparé la vitesse de calcul de 10 ^ 9 sur 2.
import time
import math
import numpy as np
x = 2
n = 10**9
#Méthode carrée itérative auto-définie
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()
#Lorsque vous utilisez votre propre méthode carrée itérative
ans1 = self_pow(x,n)
end1 = time.time()
self_pow_time1 = end1 - start
print ("time1: {0}".format(self_pow_time1) + "[sec]")
#Le pouvoir d'être incorporé
ans2 = x**n
end2 = time.time()
beki_time2 = end2 - end1
print ("time2: {0}".format(beki_time2) + "[sec]")
#Puissance intégrée
ans3 = pow(x,n)
end3 = time.time()
pow_time3 = end3 - end2
print ("time3: {0}".format(pow_time3) + "[sec]")
#numpy.power
#Puisqu'il est généralement calculé comme un entier de 32 bits
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]")
·résultat time1: 7.2481536865234375[sec] time2: 5.379794359207153[sec] time3: 5.220895767211914[sec] time4: ~~ 0.0 [sec] ~~ déborde et ne peut pas être calculé correctement, inf est affiché Erreur de débordement: erreur de plage mathématique pour math.pow
Conclusion: ~~ numpy.power est le plus rapide. ~~ Le pow intégré semble être un peu plus rapide. Ma propre fonction est lente car j'utilise while.
__2020 / 03/11 postscript __ Dans le commentaire, vous avez souligné que np.power ne pouvait pas être calculé correctement. Merci @mui_nyan. Il a également été écrit sur la page officielle. Je suis désolé. 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
Veuillez noter qu'aucune erreur ne se produira même si elle déborde.
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
La signification du théorème binomial et deux preuves Résumé de la façon de calculer l'ordre de montant de calcul! ~ D'où vient le journal ~ Je veux calculer le coefficient binomial nCr avec Python à grande vitesse Mathématiques du module Méthode de répétition du carré [[Comment trouver nCr mod m]]](https://ikatakos.com/pot/programming_algorithm/number_theory/mod_combination) Bases de la théorie cryptographique à partir d'invmod Comprendre les inverses modulaires nécessaires pour calculer 3 ÷ 4 ≡ 9 mod 11 Une fonction spéciale sur la façon de trouver "trop divisé par 1000000007"! ~ De l'élément inverse au logarithme discret ~
Recommended Posts