组合数（三种求法）

1.递推法（杨辉三角）

从 n个数不同的数中选出 m个的方案数是 ，对第一个数有选和不选两种决策，若不选，则从剩下的 n-1个中选 m个，即；若选，则从剩下的 n-1个中选 m-1个，即。

所以递推式 =+

根据公式我们发现和杨辉三角一样，当n==1，m=0时，为1；当n==3，m==2时，为3。m，n数据小的时候我们可以用递推，但如果数据范围太大就要用其他方法

void getc(){
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			if(j==0)
			a[i][j]=1; //数组a存储的是n=i,m=j的组合数
			else{
				a[i][j]=(a[i-1][j]+a[i-1][j-1])%mod;
			}
		}
	}
}

2.快速幂+乘法逆元

因为组合数太大，算法竞赛中常见问题是求解组合数取模%p（其中p为质数），=

在取模的条件下，除以一个数等价于乘以这个数的乘法逆元，例如，x /2%107=x*54%107，那么54就是 2在模107条件下的乘法逆元

1.求阶乘，求出n!，m!，(n-m)!  %p，for循环递推即可，每次乘法后取模

2.求出m!，(n-m)! 的乘法逆元（%p)，因为p为质数，所以 x的逆元即 ，用快速幂即可求出

易得，=a[n] * (a[n]的逆元）*（a[n-m]的逆元），总时间复杂度为O(n)

ll qpow(ll y,int z,int p){
	ll ans=1;
    while(y){
    	if(y&1)
    	ans*=y%p;
    	y=y*y%p;
    	y>>=1;
	}
    return ans;
}

long long c(long long n,long long m){
	if(m>n)
	return 0;
	return ((a[n]*qpow(a[m],p-2,p))%p*qpow(a[n-m],p-2,p)%p);
    //a[x]为递推求得的x的阶乘
}

3.卢卡斯定理

前半部分可以继续使用卢卡斯定理递归求解，后半部分可以用第二种方法直接求解，后半部分的m，n都会小于p，时间复杂度为O(n)。适用于n较大，p较小或n较小的情况

long long lucas(long long n,long long m){
	if(!m)  //也就是m>0
	return 1;
	return lucas(n/p,m/p)*c(n%p,m%p)%p; //前半部分为递归，后半部分 c为方法二中的函数
}