Problem Element - Find Binomial Coefficients in Number theory
Problem Statement:
Given three integers n and k, find \binom{n}{k} = \frac{n!}{k!(n-k)!}. Output the answer modulo 10^9+7
Approach:
- Precomputation of Factorials and Inverses:
- We precompute the factorials and their modular inverses up to 10^6.
- Factorial: fac[i] stores i! modulo 10^9+7.
- Inverses: We use Fermat’s Little Theorem to compute the modular inverses of the factorials: a^{−1} ≡ a^{p−2} mod p (p is prime).
- This allows us to compute k! and (n−k)! inverses efficiently.
- Binomial Coefficient Calculation:
- The formula for the binomial coefficient is given by: \binom{n}{k} = \frac{n!}{k!(n-k)!}
- Using the precomputed factorials and inverses, we can compute this in constant time: \binom{n}{k} mod p = fac[n] x inv[k] mod p x inv[n-k] mod p
- See this for reference:- Fermat Binomials in Number theory
Complexity:
- Time Complexity: Computing exponentiation will give
O(log n), computing factorial will giveO(N), computing modular inverse factorial will giveO(N+log N). Maximum Time complexity will beO(N). - Space Complexity:
O(N). To store the factorialsO(N)and inverseO(N).