ABC156 D --Bouquet I couldn't solve it without knowing the processing of the title, so make a note.
\sum_{r=0}^{n}{}_{n}{\rm C}_{r}=2^{n}
From Binomial Theorem $ (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}
The article that I referred to. The meaning of the binomial theorem and two proofs
Calculation of the binomial coefficient takes a considerable amount of time if done properly. Let's try to calculate the binomial coefficient with factorial of the math module under the conditions of n = 10 ^ 6 and 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("Exponentiation time:",sta-end1)
ab = math.factorial(n)//(math.factorial(r)*math.factorial(n-r)) #Because float overflows/Is not possible
end2 = time.time()
print("Binary calculation time:",end2-end1)
·result Exponentiation time: 0.0 sec Binary calculation time: 14.03599739074707 sec
In the competition pro, n = 10 ^ 9 is rough, so it will be TLE as it is.
Referenced articles Overview how to obtain computational complexity orders! ~ Where does the log come from ~
In most cases, the calculated value of the binomial coefficient itself is not obtained, but the remainder obtained by dividing the binomial coefficient by 10 ^ 9 + 7. In this case, there is a quick calculation method, which is realized by the following procedure.
① Pre-calculate mod (10 ^ 9 + 7) of each term of nCr
{}_{n}{\rm C}_{r} = \frac{n!}{r!(n-r)!} = (n!)(r!)^{-1}((n-r)!)^{-1}
From $ (n!) $, $ (r!) ^ {-1} $, $ ((nr)!) ^ {-1} $, divided by mod (10 ^ 9 + 7) Calculate the remainder in advance.
② Multiply the pre-calculated terms
calc_mod.py
import time
#① mod of each item of nCr(10^9+7)Pre-calculated
p = 10 ** 9 + 7
N = 10 ** 7 #Prepare as much N as you need
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1] #factinv for calculation
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)
#② Multiply the pre-calculated terms
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
Referenced articles I want to calculate the binomial coefficient nCr in Python at high speed Modulus Mathematics Repeated squares [[How to find nCr mod m]] Cryptography basics starting from invmod Understanding the modular reciprocal required to calculate 3 ÷ 4 ≡ 9 mod 11
As far as I can tell, there are five ways to do exponentiation in python. I was curious about which one was the fastest, so I investigated.
The survey method compared the speed of calculating 10 ^ 9 of 2.
import time
import math
import numpy as np
x = 2
n = 10**9
#Self-defined iterative squares
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()
#When using your own iterative squares method
ans1 = self_pow(x,n)
end1 = time.time()
self_pow_time1 = end1 - start
print ("time1: {0}".format(self_pow_time1) + "[sec]")
#Exponentiation
ans2 = x**n
end2 = time.time()
beki_time2 = end2 - end1
print ("time2: {0}".format(beki_time2) + "[sec]")
#Built-in pow
ans3 = pow(x,n)
end3 = time.time()
pow_time3 = end3 - end2
print ("time3: {0}".format(pow_time3) + "[sec]")
#numpy.power
#Since it is usually calculated as a 32-bit integer
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]")
·result time1: 7.2481536865234375[sec] time2: 5.379794359207153[sec] time3: 5.220895767211914[sec] time4: ~~ 0.0 [sec] ~~ Overflow and not calculated properly, inf is output Overflow Error: math range error for math.pow
Conclusion: ~~ numpy.power is the fastest. ~~ The built-in pow seems to be a little faster. My own function is slow because I use while.
__2020 / 03/11 postscript __ In the comment, you pointed out that np.power could not be calculated properly. Thank you @mui_nyan. It was also written on the official page. I'm sorry. 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
Please note that no error will occur even if it overflows.
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
The meaning of the binomial theorem and two proofs Overview how to obtain computational complexity orders! ~ Where does the log come from ~ I want to calculate the binomial coefficient nCr in Python at high speed Modulus Mathematics Repeated squares [[How to find nCr mod m]] Cryptography basics starting from invmod Understanding the modular reciprocal required to calculate 3 ÷ 4 ≡ 9 mod 11 A special feature on how to find "too much divided by 1000000007"! ~ From inverse element to discrete logarithm ~
Recommended Posts