Loading...
墨滴

serendipityJYH

2021/03/13  阅读:7  主题:前端之巅同款

组合数问题

组合数问题

Chapter 1 组合数的求解

一、组合数递推

 for(int i=0;i<=n;i++)c[i][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;

用于较小数据

可对应杨辉三角

例题: [BZOJ2302]-[HAOI2011]Problem c ;NOIP 2016 组合数问题

二、直接运用公式

inline ll C(ll n,ll m){
    if(n<m)return 0;
    ll ans=1;
    for(int i=0;i<m;i++){
        ll a=(n-i)%mod;
        ll b=(m-i)%mod;
        ans=ans*(a*Pow(b,mod-2)%mod)%mod;
    }
    return ans%mod;
}

用于有m较小,n较大(无法预处理)或询问次数小的情况,模数需为质数。

例题:校内OJ 组合 ;恶心的高精 洛谷P1771方程的解

三、逆元预处理

求逆元方式可见TonyYuan 【初等数论】乘法逆元略解

inline int C(int n,int m){
    if(n<m)return 0;
    return inv[n]*fac[m]%mod*fac[n-m]%mod;
}
    inv[0]=fac[0]=1;
    for(int i=1;i<=maxn;i++)
        inv[i]=inv[i-1]*i%mod;
    fac[maxn]=Pow(inv[maxn],mod-2);//费马小定理求逆元
    for(int i=maxn-1;i;i--)
        fac[i]=fac[i+1]*(i+1)%mod;

这种方法用于大部分的组合数问题,数据规模常为1 e 5-1 e 7左右,模数需为质数。

四、Lucas定理

inline int lucas(int n,int m){
    if(m==0)return 1;
    return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}

适用于数据规模较大,但m与模数中至少有一个较小的情况

n m 模数 询问次数 方法
较小 较小 无限制 杨辉三角递推
较小 较小 无限制 公式直接求
较大 较小 质数 公式直接求+费马小定理求逆元+(Lucas)
适中 适中 质数 线性预处理逆元+公式
较大 较大 质数 线性预处理逆元+Lucas
- - 无模数 - 凉心出题人 用高精吧

Chapter 2 组合数的性质(待更)

一、插板法——球盒问题

1.盒数固定,球数不固定,盒可以为空

例题: [BZOJ4403]-序列统计

二、Others

1.组合数前缀和

例题: [BZOJ4591]-[Shoi2015]超能粒子炮·改

serendipityJYH

2021/03/13  阅读:7  主题:前端之巅同款

作者介绍

serendipityJYH