Sometimes, you are asked 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↵
↵
$$↵
^nC_k = \frac{n!}{k!(n-k)!}↵
$$↵
↵
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↵
↵
$$↵
a \cdot x \equiv 1 \pmod p↵
$$↵
↵
Here, I will replace $x$ with $\text{inv}(a)$, so we have↵
↵
$$↵
a \cdot \text{inv}(a) \equiv 1 \pmod p↵
$$↵
↵
↵
Getting back to the formula for combination, we can rearrange so that↵
↵
$$↵
^nC_k = n! \cdot \frac{1}{k!} \cdot \frac{1}{(n-k)!} ↵
$$↵
↵
Here, we can use $\text{inv}(a)$ as follows↵
↵
$$↵
^nC_k \equiv n! \cdot \text{inv}(k!) \cdot \text{inv}((n-k)!) \pmod p↵
$$↵
↵
Now we can distribute the modulo to each of the terms by the distributive properties of modulo↵
↵
$$↵
^nC_k \mod p = n! \mod p \cdot \text{inv}(k!) \mod p \cdot \text{inv}((n-k)!) \mod p↵
$$↵
↵
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,↵
↵
$$↵
a^p \equiv a \pmod p↵
$$↵
↵
It is helpful to know that the $p$ in the problem ($10^9 + 7$) is indeed a prime number! We can divide both sides with $a$ to get↵
↵
$$↵
a^{p-1} \equiv 1 \pmod p↵
$$↵
↵
Looking back at our equation for $\text{inv}(a)$, both equations equate to 1, so we can equate them as↵
↵
$$↵
a \cdot \text{inv}(a) \equiv a^{p-1} \pmod p↵
$$↵
↵
Dividing each side by $a$ we have↵
↵
$$↵
\text{inv}(a) \equiv a^{p-2} \pmod p↵
$$↵
↵
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↵
↵
$$↵
a^b = (a^2)^{b/2}↵
$$↵
Every time we calculate $a^2$, we reduce the exponent by a factor of 2. We can do this repeatedly until the exponent becomes zero 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↵
↵
$$↵
a^b = a^{b-1} \cdot a↵
$$↵
↵
We then store the trailing $a$ into a variable. Then $b-1$ is 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](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#:~:text=Fermat's%20little%20theorem%20is%20the,it%20from%20Fermat's%20last%20theorem.)↵
- [Modular Multiplicative Inverse — wiki](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)↵
- [Modular Multiplicative Inverse — cp-algorithm](https://cp-algorithms.com/algebra/module-inverse.html)↵
↵
#### Problems for you↵
- [problem:300C] (Example solution: [submission:83862274])↵
- [problem:717A]↵
↵
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 andwishthank you high rating :)for reading.
↵
#### 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↵
↵
$$↵
^nC_k = \frac{n!}{k!(n-k)!}↵
$$↵
↵
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↵
↵
$$↵
a \cdot x \equiv 1 \pmod p↵
$$↵
↵
Here, I will replace $x$ with $\text{inv}(a)$, so we have↵
↵
$$↵
a \cdot \text{inv}(a) \equiv 1 \pmod p↵
$$↵
↵
↵
Getting back to the formula for combination, we can rearrange so that↵
↵
$$↵
^nC_k = n! \cdot \frac{1}{k!} \cdot \frac{1}{(n-k)!} ↵
$$↵
↵
Here, we can use $\text{inv}(a)$ as follows↵
↵
$$↵
^nC_k \equiv n! \cdot \text{inv}(k!) \cdot \text{inv}((n-k)!) \pmod p↵
$$↵
↵
Now we can distribute the modulo to each of the terms by the distributive properties of modulo↵
↵
$$↵
^nC_k \mod p = n! \mod p \cdot \text{inv}(k!) \mod p \cdot \text{inv}((n-k)!) \mod p↵
$$↵
↵
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,↵
↵
$$↵
a^p \equiv a \pmod p↵
$$↵
↵
It is helpful to know that the $p$ in the problem ($10^9 + 7$) is indeed a prime number! We can divide both sides with $a$ to get↵
↵
$$↵
a^{p-1} \equiv 1 \pmod p↵
$$↵
↵
Looking back at our equation for $\text{inv}(a)$, both equations equate to 1, so we can equate them as↵
↵
$$↵
a \cdot \text{inv}(a) \equiv a^{p-1} \pmod p↵
$$↵
↵
Dividing each side by $a$ we have↵
↵
$$↵
\text{inv}(a) \equiv a^{p-2} \pmod p↵
$$↵
↵
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↵
↵
$$↵
a^b = (a^2)^{b/2}↵
$$↵
Every time we calculate $a^2$, we reduce the exponent by a factor of 2. We can do this repeatedly until the exponent becomes zero 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↵
↵
$$↵
a^b = a^{b-1} \cdot a↵
$$↵
↵
We then store the trailing $a$ into a variable. Then $b-1$ is 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](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#:~:text=Fermat's%20little%20theorem%20is%20the,it%20from%20Fermat's%20last%20theorem.)↵
- [Modular Multiplicative Inverse — wiki](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)↵
- [Modular Multiplicative Inverse — cp-algorithm](https://cp-algorithms.com/algebra/module-inverse.html)↵
↵
#### Problems for you↵
- [problem:300C] (Example solution: [submission:83862274])↵
- [problem:717A]↵
↵
Please comment below if you know similar problems.↵
↵
↵
Stay safe and
