AcWing 887. Finding combinatorial number III (Lucas theorem)

Problem plane connection

https://www.acwing.com/problem/content/description/889/

Ideas

We will find that our modulus is much smaller than the number of combinations we require , And modulus p It's a prime number , Then we can use lucas Theorem To help us solve this problem quickly ,Lucas Theorem ：$$C_a^{b}modp=C_{amodp}^{bmodp}\times lucas(a/p,b/p)modp$$
In the mold p Under the circumstances , Then we can easily write the code for this idea , Of course, we can preprocess factorials or calculate directly when dealing with the calculation of combinatorial numbers , In the case of less visits to this topic, we can do both

About Lucas For the proof of the theorem, see ：
https://www.cnblogs.com/onlyblues/p/15339937.html

Code

Preprocessing factorials

when ：4047 ms

#include<bits/stdc++.h>
using namespace std;
//---------------- Custom part ----------------
#define ll long long
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f

int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};
const int N = 2e6+10;
ll t,n,m,q,fact[N],invfact[N],mod;
ll ksm(ll a,ll b) {
    
	ll ans = 1;
	for(;b;b>>=1LL) {
    
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){
    return -x & x;}


//---------------- Custom part ----------------


void init(){
    
	invfact[0]= fact[0] = 1;// initialization 
	for(int i = 1;i < N; ++i) {
    
		fact[i] = fact[i-1] * i % mod;
		invfact[i] = ksm(fact[i],mod-2);
	}
}
ll C(ll a,ll b){
    
	return (fact[a] * invfact[a-b]) % mod * invfact[b] % mod ;
}
ll lucas(ll a,ll b,ll p){
    
	if(a < p && b < p) return C(a,b);
	else return lucas(a/p,b/p,p) * C(a % p,b % p) % p;
}
void slove(){
    
	ll a,b;
	cin>>a>>b>>mod;
	init();
	cout<<lucas(a,b,mod)<<endl;
}

int main()
{
    
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	cin>>t;
	while(t--){
    
		slove();
	}
	
	return 0;
}

Direct calculation

when ：97ms

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


int qmi(int a, int k, int p)
{
    
    int res = 1;
    while (k)
    {
    
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int C(int a, int b, int p)
{
    
    if (b > a) return 0;

    LL resL = 1,resR = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
    
        resL = (LL)resL * j % p;
        resR = (LL)resR * i % p;
    }
    return resL * qmi(resR,p-2,p) % p;
}


int lucas(LL a, LL b, int p)
{
    
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}


int main()
{
    
    int n;
    cin >> n;

    while (n -- )
    {
    
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}