Challenge: nCr
Subdomeniu: Number Theory (number-theory)
Scor cont: 120.0 / 120
Submission status: Accepted
Submission score: 1.0
Submission ID: 464776690
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/ncr/problem
Cerinta
Given two integers $n$ and $r$. In how many ways can $r$ items be chosen from $n$ items?Input Format
The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $n$ and $r$.Output Format
Output $T$ lines, containing the required answer for the corresponding test case. Output all answers modulo $142857$.Constraints
$1 \le T \le 10^5$
$1 \le n \le 10^9$
$0 \le r \le n$Cod sursa
import functools
import sys
class MathEngine():
"""A collection of algorithms for Modular Arithmetics.
References:
[1] Granville, A. "Binomial coefficients modulo prime powers".
[2] Knuth, D. "The Art of Computer Programming", vol 1.
[3] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Polynomial_extended_Euclidean_algorithm
"""
def __init__(self):
self.pe = None
self._cache_factorial = {}
def binomial(self, n, m):
"""Find the binomial (n m) = n!/m!/(n-m)!."""
if m == 0:
if n == 0:
return 0
else:
return 1
b = self.factor_binomial(n, m)
result = self.factors_to_integer(b)
return result
def binomial_prime_power(self, n, m, p):
"""Find the max power of `p` which divides a binomial (n m)."""
result = self._number_of_carries(n-m,m,p)
return result
def factor_binomial(self, n, m):
"""Factor the binomial (n m) into primes.
The algorithm is based on Kummer's theorem [1, page 7].
Result:
{d1:p1, ..., dn:pn}, so that (n m) = d1^p1 * ... * dn^pn.
"""
result = {}
for p in self.primes(n+1):
power = self.binomial_prime_power(n,m,p)
if power > 0:
result[p] = power
return result
def factor_integer(self, n):
"""Factor n into primes.
Result:
{d1:p1, ..., dn:pn}, so that n = d1^p1 * ... * dn^pn.
"""
result = {}
for p in self.primes(n+1):
power = 0
while n % p == 0 and n != 1:
n = n // p
power += 1
if power > 0:
result[p] = power
if n == 1:
break
return result
def factor_factorial(self, n):
"""Factor the factorial of n into primes.
The algorithm is based on the Kummer's theorem formulated for binomial coefficients;
for the case of factorials see [1, eq.(17)] or [2, eq.(1.2.5.8)].
Result:
{d1:p1, ..., dn:pn} such that n! = d1^p1 * ... * dn^pn.
"""
result = {}
for prime in self.primes(n+1):
k = n
result[prime] = 0
while k > 0:
k = k // prime
result[prime] += k
return result
def factorial(self, n, p=0, mod=0):
"""Find the product of all integers <= n, i.e. the factorial of n;
if p > 0 exclude integers divisible by p; if mod > 0 find result
modulo mod."""
_cache_key = (n,p,mod)
if _cache_key in self._cache_factorial:
return self._cache_factorial[_cache_key]
result = 1
if p == 0:
if mod == 0:
for k in range(1,n+1):
result *= k
else:
for k in range(1,n+1):
result = (result*k) % mod
else:
if mod == 0:
for k in range(1,n+1):
if k % p != 0:
result *= k
else:
for k in range(1,n+1):
if k % p != 0:
result = (result*k) % mod
self._cache_factorial[_cache_key] = result
return result
def factors_to_integer(self, n):
result = 1
for prime,power in n.items():
result *= prime**power
return result
def gcd_extended(self, a, b):
"""Find gcd(a,b) and coefficients s,t of the Bezout's identity, such that
`a*s + b*t = gcd(a,b)`. See [3] for more details.
Result:
(gcd(a,b), s, t)
"""
s, s_old = 0, 1
t, t_old = 1, 0
r, r_old = b, a
while r != 0:
k = r_old // r
r_old, r = r, r_old - k * r
s_old, s = s, s_old - k * s
t_old, t = t, t_old - k * t
return r_old, s_old, t_old
def integer_digits(self, n, p):
"""Find digits of n in the p representation.
Result:
[a0,...,ak], such that n = a0 + a1*p + ... + ak*p^k, where ai < p.
"""
result = []
while n > 0:
result.append(n % p)
n //= p
return result
def integer_digits_len(self, n, p):
result = 1
while n > 0:
result += 1
n //= p
return result
def mod_binomial(self, n, m, mod):
"""Find the reminder from the division of the binomial (n m) by mod.
The algorithm is simple and slow, but less prone to errors comparing
to the faster and more complex generalized Lucas algorithm, for more
details see `mod_binomial_lucas` method.
"""
binomial_factors = self.factor_binomial(n, m)
result = 1
for prime, exp in binomial_factors.items():
result = (result * pow(prime, exp, mod)) % mod
return result
def mod_binomial_lucas(self, n, m, p, q=1):
"""Find the reminder form the division of the binomial (n m) by p^q,
where mod is a prime number. This routine employs Lucas' Theorem (for q=1)
and its generalization for (q>1), see [1, Theorem 1].
"""
e0 = self.binomial_prime_power(n,m,p)
qq = q-e0
if qq < 0:
return 0
p_e0, p_q, p_qq = p**e0, p**q, p**qq
r = n - m
d = self.integer_digits_len(n, p)
_ni, _mi, _ri = n, m, r
_least_positive_residue_n = []
_least_positive_residue_m = []
_least_positive_residue_r = []
for i in range(0, d):
_least_positive_residue_n.append(_ni % p_qq)
_least_positive_residue_m.append(_mi % p_qq)
_least_positive_residue_r.append(_ri % p_qq)
_ni //= p
_mi //= p
_ri //= p
_factorial = [1]
curr = 1
for x in range(1,p_qq):
if x % p != 0:
curr = (curr*x) % p_qq
_factorial.append(curr)
result, i = 1, 0
aaa, bbb, ccc = 1, 1, 1
for i in range(0, d):
aa = _least_positive_residue_n[i]
bb = _least_positive_residue_m[i]
cc = _least_positive_residue_r[i]
a = _factorial[aa]
b = _factorial[bb]
c = _factorial[cc]
aaa = (aaa*a) % p_qq
bbb = (bbb*b) % p_qq
ccc = (ccc*c) % p_qq
i += 1
result = aaa * self.mod_inverse(bbb*ccc % p_qq, p_qq) % p_qq
if p != 2 or qq < 3:
result *= (-1)**self._number_of_carries(m,r,p,qq-1)
result = (result * p_e0) % p_q
return result
def _least_positive_residue(self, n, j, p, q):
"""Helper for mod_binomial_lucas method"""
result = (n//p**j) % p**q
return result
def _number_of_carries(self, m, r, p, j=0):
"""Helper for mod_binomial_lucas method"""
result, carry, jj = 0, 0, 0
while (m > 0 or r > 0):
if (m % p) + (r % p) + carry >= p:
carry = 1
else:
carry = 0
if jj >= j:
result += carry
m, r = m // p, r // p
jj += 1
return result
def mod_chinese(self, rs):
n = functools.reduce(lambda a,b: a*b, rs.keys(), 1)
result = 0
for ni,ai in rs.items():
nn = n // ni
_, ri, si = self.gcd_extended(ni, nn)
ei = si*nn
result += ai*ei
result = result % n
return result
def mod_inverse(self, n, mod):
r, s, t = self.gcd_extended(n, mod)
if r != 1:
return None
return s
def primes(self, n):
return self.pe.primes(n)
class Solver(object):
def __init__(self):
self.me = MathEngine()
self.mod = 142857
def solution(self, n, r):
"""Find solution to the "nCr" problem."""
mod_factors = {3: 3, 11: 1, 13: 1, 37: 1}
mods = {p**q:self.me.mod_binomial_lucas(n, r, p, q) for p,q in mod_factors.items()}
result = self.me.mod_chinese(mods)
return result
if __name__ == '__main__':
T = int(sys.stdin.readline())
solver = Solver()
for i in range(T):
n, r = [int(num) for num in sys.stdin.readline().split()]
print(solver.solution(n, r))
HackerRank Number Theory – nCr