CP_Templates.py

defdisplay(string_to_print):
stdout.write(str(string_to_print) +"\n")


deffast_exp(base, power):
result=1
whilepower>0:
ifpower%2==1:
result= (result*base) %m
power=power//2
base= (base*base) %m
returnresult


# n**0.5 complexity 
defprime_factors(n): 
factors=dict()
foriinrange(2, math.ceil(math.sqrt(n)) +1):
whilen%i==0:
ifiinfactors:
factors[i] +=1
else:
factors[i] =1
n=n//i
ifn>2:
factors[n] =1
return (factors)


defall_factors(n):
returnset(reduce(list.__add__,([i, n//i] foriinrange(1, int(n**0.5) +1) ifn%i==0)))


deffibonacci_modP(n, MOD):
ifn<2: return1
return (cached_fn(fibonacci_modP, (n+1) //2, MOD) *cached_fn(fibonacci_modP, n//2, MOD) +cached_fn(fibonacci_modP, (n-1) //2, MOD) *cached_fn(fibonacci_modP, (n-2) //2, MOD)) %MOD


deffactorial_modP_Wilson(n, p):
if (p<=n):
return0
res= (p-1)
foriinrange(n+1, p):
res= (res*cached_fn(InverseEuler, i, p)) %p
returnres


defbinary(n, digits=20):
b=bin(n)[2:]
b='0'* (digits-len(b)) +b
returnb


defis_prime(n):
"""Returns True if n is prime."""
ifn<4:
returnTrue
ifn%2==0:
returnFalse
ifn%3==0:
returnFalse
i=5
w=2
whilei*i<=n:
ifn%i==0:
returnFalse
i+=w
w=6-w
returnTrue

# Sieve of Eratosthenes 
defsieve(n):
prime= [Trueforiinrange(n+1)]
p=2
whilep*p<=n:
ifprime[p]:
foriinrange(p*2, n+1, p):
prime[i] =False
p+=1
returnprime

# O(nlog(logn))



factorial_modP= []


defwarm_up_fac(MOD):
globalfactorial_modP, fac_warm_up
iffac_warm_up: return
factorial_modP= [1for_inrange(fac_warm_up_size+1)]
foriinrange(2, fac_warm_up_size):
factorial_modP[i] = (factorial_modP[i-1] *i) %MOD
fac_warm_up=True


defInverseEuler(n, MOD):
returnpow(n, MOD-2, MOD)

defnCk(n, k): 
if(k>n-k): 
k=n-k
res=1
foriinrange(k): 
res=res* (n-i) 
res=res/ (i+1) 
returnres

defnCr(n, r, MOD):
globalfac_warm_up, factorial_modP
ifnotfac_warm_up:
warm_up_fac(MOD)
fac_warm_up=True
return (factorial_modP[n] * (
 (pow(factorial_modP[r], MOD-2, MOD) *pow(factorial_modP[n-r], MOD-2, MOD)) %MOD)) %MOD


deftest_print(*args):
iftestingMode:
print(args)


defdisplay_list(list1, sep=" "):
stdout.write(sep.join(map(str, list1)) +"\n")


defdisplay_2D_list(li):
foriinli:
print(i)


defprefix_sum(li):
sm=0
res= []
foriinli:
sm+=i
res.append(sm)
returnres


defget_int():
returnint(stdin.readline().strip())


defget_tuple():
returnmap(int, stdin.readline().split())


defget_list():
returnlist(map(int, stdin.readline().split()))


memory=dict()


defclear_cache():
globalmemory
memory=dict()


defcached_fn(fn, *args):
globalmemory
ifargsinmemory:
returnmemory[args]
else:
result=fn(*args)
memory[args] =result
returnresult


defncr(n, r):
returnmath.factorial(n) / (math.factorial(n-r) *math.factorial(r))


defbinary_search(i, li):
fn=lambdax: li[x] -x//i
x=-1
b=len(li)
whileb>=1:
whileb+x<len(li) andfn(b+x) >0: # Change this condition 2 to whatever you like
x+=b
b=b//2
returnx