组合数

从 $1,2,3,...,n$ 中选择 $m$ 个数的方案数，记为 $\dbinom{n}{m}$，也可记为 $C^m_n$。读作 “$n$ 取 $m$”。$\dbinom{n}{m}=\frac{n!}{m!(n-m)!}$

$O(n^2)$

引理：在杨辉三角中的第 $n$ 行 $m$ 列等于 $\dbinom{n}{m}$。 根据这个引理，我们可以用构造杨辉三角的形式构造组合数。 杨辉三角的构造很简单，就是当前位等于上面的加左上的，也就是 $a_{i,j}=a_{i-1,j}+a_{i-1,j-1}$，转换成组合数就是 $\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$。

时间复杂度 $O(n^2)$。

注意点 1.注意边界 $\dbinom{0}{0}=1$。

code

B2164 组合数问题

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=5050,mod=1e9+7;
int c[N][N];
void get_c(int n){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=i;j++){
			if(!j)c[i][j]=1;
			else c[i][j]=c[i-1][j]+c[i-1][j-1];
            c[i][j]%=mod;
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	get_c(max(n,m));
	cout<<c[n][m]%mod;
	return 0;
}

$O(n)$

展开 $\dbinom{n}{m}=\frac{n!}{m!(n-m)!}$，发现这个式子可以直接使用阶乘求解，但是答案一般都很大，除法又正好不满足同余定理，所以这时，要用逆元来解决。

由逆元的定义可得 $\dbinom{n}{m}=n!\times inv_{m!}\times inv_{(n-m)!}$，所以只要预处理 $1$ 到 $n$ 的阶乘逆元，最终答案就是 $n!\times inv_{m!}\times inv_{(n-m)!}$。

时间复杂度 $O(n+\log p)-O(1)$。 注意点 1.注意在求组合数时可以模，因为转换成了逆元。

code

B3717 组合数问题

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int n,m;
typedef unsigned long long ll;
const ll mod=998244353;
ll qpow(ll a,ll b,ll p){
	ll res=1;
	a%=p;
	while(b){
		if(b&1){
			res=res*a%p;
		}
		a=a*a%p;
		b>>=1;
	}
	return res;
}
int T,Q;
ll inv[N];
ll fact[N];
void init(int n){
	fact[0]=1;
	for(int i=1;i<=n;i++){
		fact[i]=fact[i-1]*i%mod;
	}
	int k=qpow(fact[n],mod-2,mod);
	inv[n]=k;
	for(int i=n;i>=1;i--){
		inv[i-1]=inv[i]*i%mod;
	}
}
ll C(ll n,ll m){
	return fact[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T>>Q;
	init(Q);
	ll res=0;
	while(T--){
		cin>>n>>m;
		res^=C(n,m);
	}
	cout<<res;
	return 0;
}

二项式定理

我们早就学过，杨辉三角的第 $n$ 行就是 $(a+b)^n$ 的展开式的各项系数，所以我们可以根据杨辉三角和组合数的关系，推出如下式子：

$$(a+b)^n=\sum^n_{i=0}\dbinom{n}{i}a^{n-i}b^i$$

这个展开式首先就要把每一位加上，所以要用求和。$\dbinom{n}{i}$ 表示的是杨辉三角第 $n$ 行的第 $i$ 个数，也就是这一位的系数。因为 $(a+b)^n$ 的每一项的指数和都是 $n$，且 $a$ 的指数逐渐减少， $b$ 的指数是逐渐增大。注意可以 $i=0$，因为有 $a^0=b^0=1$ 作为系数，省略。