题解 | 【模板】组合数

#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long ll; 

const ll p = 1000000007;
const ll biggest = 500000; 
ll factorial[biggest], inverse[biggest];


ll fast_pow_mod(ll base, ll exp, ll p) {
	if (base == 0) return 0;
	ll ans = 1;
	while (exp > 0) {
		if(exp & 1) ans = (ans * base) % p;
		base = (base * base) % p;
		exp >>= 1;
	}
	return ans;
}

//计算m * (m - 1) * ... *(m - n + 1)，  这种方式单次是o(n),总时间o(n * t)超时 
//ll factorial(ll m, ll n, ll p) {
//	ll result = 1;
//	while (n-- > 0) {
//		result = (result * m) % p;
//		m--;
//	}
//	return result;
//}

//比较容易踩坑的点c(m,n)中, m >= 0, n >= 0且c(0,0) = 1
//对于阶乘而言0! = 1,所以即使n = 0 / n = m两种情况下依旧可以求出n!和(n - m)!的逆元
int main() {
	//预处理
	factorial[0] = 1;
	factorial[1] = 1;
	for (int i = 2;i <= biggest; i++) {
		factorial[i] = factorial[i - 1] * i % p;
	}
	for (int i = 0; i <= biggest; i ++) {
		inverse[i] = fast_pow_mod(factorial[i], p - 2, p);
	} 
	ll m, n;
	int t;
	cin >> t;
	while (t-- > 0) {
		cin >> n >> m;
		//C m n
//		ll a = factorial(m, n, p);
//		ll b = factorial(n, n, p);
//		ll inverse = fast_pow_mod(b, p - 2, p);
		ll ans;
		ans = ((factorial[m] * inverse[n]) % p) * inverse[m - n] % p;
//		ans = ((factorial[m] * inverse[n]) % p) * inverse[m - n] % p;
		cout << ans << endl;
	}
}