It is common for competitive programming problems to ask you to calculate the combination or permutation modulo a number, for example $$$^nC_k \mod p$$$. Here I want to write about a complete method to solve such problems with a good time complexity because it took me a lot of googling and asking to finally have the complete approach. I hope this blog can help other users and save their time when they solve combinatorics problem in Codeforces.
Example Problem
Find the value of $$$^nC_k$$$, ($$$1 \leq n,k \leq 10^6$$$). As this number can be rather large, print the answer modulo $$$p$$$. ($$$p = 1000000007 = 10^9 + 7$$$)
Combination (binomial coefficients)
$$$^nC_k$$$ means how many ways you can choose $$$k$$$ items from an array of $$$n$$$ items, also denoted as $$$\binom{n}{k}$$$. This is also known as binomial coefficients. The formula for combination is
Sometimes, the denominator $$$k!(n-k)!$$$ is very large, but we can't modulo it since modulo operations can't be done independently on the denominator. $$$\frac{n!}{k!(n-k)!} \mod p \neq \frac{n! \mod p}{k!(n-k)! \mod p}$$$. Now I will introduce the modular multiplicative inverse to solve this problem.
Modular multiplicative inverse
The modular multiplicative inverse $$$x$$$ of $$$a$$$ modulo $$$p$$$ is defined as
Here, I will replace $$$x$$$ with $$$\text{inv}(a)$$$, so we have
Getting back to the formula for combination, we can rearrange so that
Here, we can use $$$\text{inv}(a)$$$ as follows
Now we can distribute the modulo to each of the terms by the distributive properties of modulo
Now I will discuss on how to calculate $$$\text{inv}(a)$$$
Fermat's Little Theorem
You can easily remember this theorem. Let $$$a$$$ be an integer and $$$p$$$ be a prime number,
It is helpful to know that the $$$p$$$ in the problem ($$$10^9 + 7$$$) is indeed a prime number! We can rearrange it to be
Looking back at our equation for $$$\text{inv}(a)$$$, both equations equate to 1, so we can equate them as
Dividing each side by $$$a$$$ we have
We now have a directly formula for $$$\text{inv}(a)$$$. However, we cannot use the pow()
function to calculate $$$a^{p-2}$$$ because $$$a$$$ and $$$p$$$ is a large number (Remember $$$1 \leq n,k \leq 10^6$$$) ($$$p = 10^9 + 7$$$). Fortunately, we can solve this using modular exponentiation.
Modular Exponentiation
To prevent integer overflow, we can carry out modulo operations during the evaluation of our new power function. But instead of using a while loop to calculate $$$a^{p-2}$$$ in $$$O(p)$$$, we can use a special trick called squaring the powers. Note that if $$$b$$$ is an even number
Every time we calculate $$$a^2$$$, we reduce $$$b$$$ by a factor of 2. We can do this repeatedly until $$$b=0$$$ where we stop the loop. This will give us a time complexity of $$$O(\log p)$$$ to calculate $$$a^{p-2}$$$ because we halve the exponent in each step. For the case when $$$b$$$ is odd, we can use the property
Then $$$b$$$ will become even and we can proceed as previously stated. We can repeatedly apply these two equations to calculate $$$a^{p-2}$$$. Here I will show you the implementation of this modified powmod()
function to include modulo operations. ll
is defined as long long
ll powmod(ll a, ll b, ll p){
a %= p;
if (a == 0) return 0;
ll product = 1;
while(b > 0){
if (b&1){ // you can also use b % 2 == 1
product *= a;
product %= p;
--b;
}
a *= a;
a %= p;
b /= 2; // you can also use b >> 1
}
return product;
}
Then we can finally implement the $$$\text{inv}(a)$$$ function simply as
ll inv(ll a, ll p){
return powmod(a, p-2, p);
}
Then, finally, we can implement $$$^nC_k$$$ as
ll nCk(ll n, ll k, ll p){
return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n-k], p)) % p;
}
We used the dp-approach for factorial where the factorial from 1 to n is pre-computed and stored in an array fact[].
Time complexity
- Pre-computation of factorial: $$$O(n)$$$
- Calculation of $$$^nC_k$$$, which is dominated by modular exponentiation
powmod
: $$$O(\log p)$$$ - Total: $$$O(n + \log p)$$$
Reference
- Fermat's Little Theorem — wiki
- Modular Multiplicative Inverse — wiki
- Modular Multiplicative Inverse — cp-algorithm
Problems for you
Please comment below if you know similar problems.
Thank you for reading. I hope this blog will help you in your competitive programming journey. Stay safe and wish you high rating :)