AcWing 886. Finding combinatorial number II (pretreatment factorial)

Topic link

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

Ideas

This data range is even larger , So we can't use recursion at this time , Because I can't save it , Second, the complexity is too high , So we can start from the definition of combinatorial number ：$C_a^b=\frac{a!}{(a-b)!\times b!}$, So now we just need to 1e5 All factorials within and the inverse preprocessing of factorials are OK , So the problem is solved

Code

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

int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

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;}

const int N = 2e6+10;
//---------------- Custom part ----------------
ll t,n,m,q,fact[N],invfact[N];

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);
	}
}
void slove(){
    
	ll a,b;
	cin>>a>>b;
	cout<<(fact[a] * invfact[a-b]) % mod * invfact[b] % mod <<endl;
}

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