Expert · Number theory · 242 of 264
Combinations modulo a prime
Compute C(n, k), the number of ways to choose k items out of n, modulo 1000000007, for n up to 200000. Precompute factorials and use modular inverses (Fermat).
Input: n and k on one line (0 <= k <= n). Output: C(n, k) mod 1000000007
Examples
Input
5 2
Output
10
Input
10 0
Output
1
Input
200000 100000
Output
879467333
One more test checks other inputs when you press Check.
Stuck? The idea behind number theory
Whole-number tricks: n % d == 0 means d divides n; test divisors only up to the square root; the sieve of Eratosthenes finds every prime up to n at once.
pow(a, b, m) works out a to the power b, modulo m, quickly, even when the power is huge.
n = 50
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
print(sum(is_prime))Watch for: Testing every number up to n one by one is too slow for big inputs: the hidden tests notice.