大规模组合数计算之费马小定理之逆元

大规模组合数计算，利用帕斯卡恒等式的递归会超时，利用帕斯卡三角形（杨辉三角）的递推会超存储。

必须直接使用组合数的计算公式：*****)=n!/(m!*(n-m)!)
数值较大，一般对某个数值取模之后的结果。

取模运算对加、减、乘封闭，直接使用组合数计算公式涉及到除法运算，运算过程中进行取模会导致错误，因此要使用到逆元概念：a^(p-2) ≡ 1/a (mod p)，将除法转换成其他运算。

逆元概念和计算方式来源于费马小定理：如果p是质数，且整数a不是p的倍数，那么一定有a^(p−1) ≡ 1(mod p)。两边分别除以非p倍数的a即可得到逆元的计算公式。

有了逆元计算公式，则：*****)%MOD = n!/(m!*(n-m)!)%MOD，可以转换成 n!*(1/m!)%MOD*(1/(n-m)!)%MOD。除法变乘法，取余运算封闭。

#include <iostream>
using namespace std;
const int MOD = 1000000007;
const int N = 1000005;
long long fact[N];     // 阶乘数组
long long inv_fact[N]; // 逆元阶乘数组

// 快速幂：计算 a^b % MOD
long long qpow(long long a, long long b) {
	long long res = 1;
	while (b > 0) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

// 预处理阶乘和逆元阶乘
void init() {
	fact[0] = 1;
	for (int i = 1; i < N; i++) {
		fact[i] = fact[i-1] * i % MOD;
	}
	// 求最大阶乘的逆元
	inv_fact[N-1] = qpow(fact[N-1], MOD-2);
	// 倒推所有逆元阶乘
	//i!=(i+1)!÷(i+1)  两边同时取逆元（模意义下）  
	//inv(i!)=inv((i+1)!÷(i+1))  模意义下，除以 (i+1) 等于乘以它的逆元
	//inv(i!)=inv((i+1)!)*(i+1)% MOD
	for (int i = N-2; i >= 0; i--) {
		inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
	}
}

int main() {
	init();

	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		// 组合数公式 
		long long ans = fact[n] * inv_fact[k] % MOD;
		ans = ans * inv_fact[n - k] % MOD;
		cout << ans << '\n';
	}
	return 0;
}