写这个类型博客的目的就是想总结一下某个专题的知识点，方便以后比赛前复习，由于太菜，如有错误，还请斧正。

首先不知道组合数的同学先自行百度（虽然应该没有人）

先说说组合数的几种求法（以下代码参考自宝藏数论文章https://www.cnblogs.com/linyujun/p/5194189.html）

1.递推（在数量级比较小的情况下使用）O（n^2）

const int N = 2000 + 5;
const int MOD = (int)1e9 + 7;
int comb[N][N];
void init(){
    for(int i = 0; i < N; i ++){
        comb[i][0] = comb[i][i] = 1;
        for(int j = 1; j < i; j ++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
            comb[i][j] %= MOD;
        }
    }
}

2.逆元法O(n)一般够用了

const int N = 200000 + 5;
const int MOD = (int)1e9 + 7;
int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘 
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < N; i ++){
        F[i] = F[i-1] * 1ll * i % MOD;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
    }
}
int comb(int n, int m){
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}

3.卢卡斯定理

应对c(n,m)%p中n,m很大且p较小且p为质数的情况

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int quick_power_mod(int a,int b,int m)//pow(a,b)%m
{
	int result = 1;
	int base = a;
	while(b>0)
	{
		if(b&1==1)
		result=(result*base)%m;
		base=(base*base)%m;
		b>>=1;
	}
	return result;
}
//计算组合数取模
ll comp(ll a,ll b,int p)//composite num C(a,b)%p
{
	if(a<b)return 0;
	if(a==b)return 1;
	if(b>a-b)b=a-b;
	int ans=1,ca=1,cb=1;
	for(ll i=0;i<b;i++)
	{
		ca=(ca*(a-i))%p;
		cb=(cb*(b-i))%p;
	}
	ans=(ca*quick_power_mod(cb,p-2,p))%p;
	return ans;
}
ll lucas(ll n,ll m,ll p)
{
	ll ans=1;
	while(n&&m&&ans)
	{
		ans=(ans*comp(n%p,m%p,p))%p;//also can be recusive
		n/=p;
		m/=p;
	}
	return ans;
}