求组合数

方案一：打表

c(n , m) = c(n-1 , m)+c(n-1 , m-1) 适用范围n<=1000;

方案二：质因数分解没有用过谢大佬模板

https://segmentfault.com/a/1190000005072018

代码量有点大不推崇时间复杂度 1是大约可以进行1e7的计算

//用筛法生成素数
const int MAXN = 1000000;
bool arr[MAXN+1] = {false};
vector<int> produce_prim_number()
{
    vector<int> prim;
    prim.push_back(2);
    int i,j;
    for(i=3; i*i<=MAXN; i+=2)
    {
        if(!arr[i])
        {
            prim.push_back(i);
            for(j=i*i; j<=MAXN; j+=i)
                arr[j] = true;
        }
    }
    while(i<=MAXN)
    {
        if(!arr[i])
            prim.push_back(i);
        i+=2;
    }
    return prim;
}

//计算n!中素因子p的指数
int Cal(int x, int p)
{
    int ans = 0;
    long long rec = p;
    while(x>=rec)
    {
        ans += x/rec;
        rec *= p;
    }
    return ans;
}

//计算n的k次方对M取模，二分法
int Pow(long long n, int k, int M)
{
    long long ans = 1;
    while(k)
    {
        if(k&1)
        {
            ans = (ans * n) % M;
        }
        n = (n * n) % M;
        k >>= 1;
    }
    return ans;
}

//计算C(n,m)
int Combination(int n, int m)
{
    const int M = 10007;
    vector<int> prim = produce_prim_number();
    long long ans = 1;
    int num;
    for(int i=0; i<prim.size() && prim[i]<=n; ++i)
    {
        num = Cal(n, prim[i]) - Cal(m, prim[i]) - Cal(n-m, prim[i]);
        ans = (ans * Pow(prim[i], num, M)) % M;
    }
    return ans;
}

方案三：lucas定理

lucas适用于 n , m可以很大但是取余的数字mod不可以大于1e5

代码如下

long long mod_pow(int a,int n,int p)
{
    long long ret=1;
    long long A=a;
    while(n)
    {
        if (n & 1)
            ret=(ret*A)%p;
        A=(A*A)%p;
        n>>=1;
    }
    return ret;
}
 
long long factorial[N];
 
void init(long long p)
{
    factorial[0] = 1;
    for(int i = 1;i <= p;i++)
        factorial[i] = factorial[i-1]*i%p;
    //for(int i = 0;i < p;i++)
        //ni[i] = mod_pow(factorial[i],p-2,p);
}
 
long long Lucas(long long a,long long k,long long p) //求C(n,m)%p p最大为10^5。a,b可以很大！
{
    long long re = 1;
    while(a && k)
    {
        long long aa = a%p;long long bb = k%p;
        if(aa < bb) return 0; //这个是最后的改动！
        re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;//这儿的求逆不可先处理
        a /= p;
        k /= p;
    }
    return re;
}

方案四：扩展欧几里得

代码如下：

LL fac[MAXL+50];//求阶乘
void inite()
{
    fac[0]=fac[1]=1;
    for(LL i=2; i<=MAXL; i++)
        fac[i]=fac[i-1]*i%mod;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    LL ans=exgcd(b,a%b,x,y);
    LL temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}
LL niYuan(LL a, LL b)
{
    LL x, y;
    exgcd(a, b, x, y);
    return (x + b) % b;
}
LL C(LL a, LL b)
{
    return fac[a]*niYuan(fac[b],mod)%mod*niYuan(fac[a-b],mod)%mod;
}

ps: 扩展欧几里得是一个递进的过程首先可以求得方程的解之后可以递推到求逆元，再进一步可以推到求组合数