组合数定义

$C_a^b=\frac{a!}{b!(a-b)!}$

带模数

数据范围(a 、b较小)

$1\le n\le 10000$,
$1\le b\le a\le 2000$

$mod=1e9+7$

$C_i^j==C_{i-1}^j+C_{i-1}^{j-1}$

const int N = 2005;

int ans[N][N];
void init() {
    // 递推预处理
	for (int i = 0;i < N;++i) {
   
		for (int j = 0;j <= i;++j) {
   
			if (!j)ans[i][j] = 1;
			else ans[i][j] = (ans[i - 1][j] + ans[i - 1][j - 1]) % mod;
		}
	}
}

int main() {
   
	init();

	int n;cin >> n;
	while (n--) {
   
		int a, b;cin >> a >> b;
		printf("%d\n", ans[a][b]);
	}

	return 0;
}

数据范围(a、b较大)

$1\le n\le 10000,$
$1\le b\le a\le 10^5$

$mod=1e9+7$

const int N = 100010;

int fact[N], infact[N];

int qmi(int a, int b) {
   
	int res = 1;
	while (b) {
   
		if (b & 1)res = (LL)res * a % mod;
		a = (LL)a * a % mod;
		b >>= 1;
	}
	return res;
}
int main() {
   
	fact[0] = infact[0] = 1;
	for (int i = 1;i < N;++i) {
   
		fact[i] = (LL)fact[i - 1] * i % mod;
		infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod; //求逆元
	}

	int n;cin >> n;
	while (n--) {
   
		int a, b;
		cin >> a >> b;
		printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
	}

	return 0;
}

数据范围(a、b非常大)

$1\le n\le 20$
$1\le b\le a\le 10^{18}$
$1\le p\le 10^5$

卢卡斯定理

$C_a^b\equiv C_{amodp}^{bmodp}\cdot C_{a/p}^{b/p}(modp)$

const int N = 100010;

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

int C(int a, int b) {
   
	if (b > a)return 0;
	int res = 1;
	for (int i = 1, j = a;i <= b;++i, --j) {
   
		res = (LL)res * j % p;
		res = (LL)res * qmi(i, p - 2) % p;
	}
	return res;
}

int lucas(LL a, LL b) {
   
	if (a < p && b < p)return C(a, b);
	return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
int main() {
   
	
	int n;cin >> n;
	while (n--) {
   
		LL a, b;
		cin >> a >> b >> p;
		cout << lucas(a, b) << endl;
	}

	return 0;
}

无模数

数据范围

$1\le b\le a\le 5000$

根据$C_a^b=\frac{a!}{b!(a-b)!}$

等式右边分子分母分解质因数后约掉 再用高精度乘法

——------------------------------------------------------------------------------------------------------------------------------------

const int N = 100010;
bool st[N];
int primes[N], cnt;
int sum[N];
//欧拉筛
void get_primes(int n) {
   
	for (int i = 2;i <= n;++i) {
   
		if (!st[i]) {
   
			primes[cnt++] = i;
		}
		for (int j = 0;primes[j] <= n / i;++j) {
   
			st[primes[j] * i] = true;
			if (i % primes[j] == 0)break;
		}
	}
}
//求n的阶乘中 质因子p的次数
int get(int n, int p) {
   
	int res = 0;
	while (n) {
   
		res += n / p;
		n /= p;
	}

	return res;
}
//高精度乘法
vector<int>mul(vector<int>a, int b) {
   
	vector<int >c;
	int t = 0;
	for(int i = 0;i < a.size() || t;++i){
   
		if(i < a.size())t += a[i] * b;
		c.push_back(t % 10);
		t /= 10;
	}

	return c;
}
int main() {
   
	int a, b;cin >> a >> b;

	get_primes(a);

	for (int i = 0;i < cnt;i++) {
   
		int p = primes[i];
		sum[i] = get(a,p) - get(b,p) - get(a - b,p);//最终结果中质因子p的次数
	}

	vector<int>ans;
	ans.push_back(1);
//因为数据太大可能会溢出LL 所以不用快速幂 用高精度乘法
	for (int i = 0;i < cnt;++i) {
   
		for (int j = 0; j < sum[i];++j) {
   
			ans = mul(ans, primes[i]);//将最终化简结果的质因数分解形式变成原来的数据
		}
	}

	for (int i = ans.size() - 1;i >= 0;--i)printf("%d", ans[i]);
	cout << endl;
	return 0;
}

卡特兰数

$C_{2n}^n-C_{2n}^{n-1}$ $=\frac{C_{2n}^n}{n-1}$

从$(0,0)$到$(n,n)$所有不经过对角线的路径方案数

所有可能的路径数$C_{2n}^n$

不满足条件的路径为经过红线的路径 $C_{2n}^{n-1}$

所以满足条件的方案数为$C_{2n}^n-C_{2n}^{n-1}$ $=\frac{C_{2n}^n}{n-1}$ 即为卡特兰数