Find the number of combinations (the strongest optimization)

Simple optimization （ No modulo operation ）

When m < n-m when , hold n - m Change it to m, Use the following algorithm , Simple optimization
$$C_n^m=C_n^{n-m}$$
The code is as follows ：

#include<cstdio>
using namespace std;
long long C(int n, int m){
	if (m<n-m)	m=n-m;
	long long ans=1;
	for (int i=m+1;i<=n;i++) ans *= i;
	for (int i=1;i<=n-m;i++) ans /= i;
	return ans;
}
int main(){
	printf("%lld\n",C(n,m));
	return 0;
}

Advanced optimization （ Inverse element - Modular of combinatorial data ）

problem ： seek $C_n^m$%p（ classic p=1e9+7）

stay $C_n^m$ Operation , Modulus property does not apply to divisor , Need to put “ division ” Convert to “ Multiplication ”, Only with the help of the nature of the module can we not explode long long Calculate the number of combinations . And that's where it comes in “ Inverse element ”！

Inverse element ： about a and p（a and p Relatively prime ）, if a*b%p≡1, said b by a%p Inverse element .

What's the use of this inverse element ？ Imagine begging ( $\frac{a}{b}$ )%p, If you know b%p The inverse element of is c, It can be transformed into ( $\frac{a}{b}$ )%p = a*c%p = (a%p)(c%p)%p

How to find the inverse element ？ At this time, we need to introduce the powerful Fermat theorem ！

Fermat's small Theorem ： about a And prime numbers p, Satisfy $ a^{p-1} $ %p≡1

And then because $ a^{p-1} $ =$a^{p-2}$ ∗a, So there is $a^{p-2}$∗a%p≡1！ By comparing the definition of inverse element ,$a^{p-2}$ yes a Inverse element ！

So the problem is transformed into solving $a^{p-2}$, That is, it becomes the problem of finding the fast power （ Of course, this needs to be met p As a prime number ）.

Please refer to another article of blogger for quick power ： Fast power algorithm

Now summarize the solution $C_n^m$%p Steps for ：

1. Through the loop , Calculate in advance all less than max_number The factorial （ %p ） Result , Deposit in fac[max_number] in ( fac[i] = i ! %p )
2. seek m!%p Inverse element （ The o fac[m] Inverse element ）： According to Fermat's theorem ,x%p The inverse element of is $x^{p-2}$, So by fast exponentiation , solve $fac[m{]}^{p-2}$ %p, Write it down as M
3. seek (n-m)!%p Inverse element ： Similarly, it is to solve $fac[n-m{]}^{p-2}$%p, Write it down as NM
4. $C_n^m$%p = ( ( fac[n] * M)%p * NM)%p

use C++ Implemented code , Input is n,m,p, requirement 0<=m<=n<=1e6（ otherwise fac There is no room for ）, And gcd(p,n!)=1（ Namely mutual prime ）, Output is Cmn%p

long long fac[MAXN];
long long n,m,p;
// Fast exponentiation x^n%mod 
long long pow_mod(long long x, long long n, long long mod) {
    long long res=1;
    while(n){
        if(n&1)  res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
int main() {
    while(~scanf("%lld %lld %lld", &n, &m, &p)) {        
        // Pretreatment requires fac,fac[i]=i!%p
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {fac[i] = fac[i - 1] * i % p;}
        // Combinatorial number  = n!*(m!%p Inverse element )*((n-m)!%p Inverse element )%p 
        printf("%lld\n", fac[n] * pow_mod(fac[m], p - 2, p) % p * pow_mod(fac[n - m], p - 2, p) % p);
    }
}

Reference link —— Inverse element - Modular of combinatorial data