组合计数

luckydrawbox · 2021-08-27 22:51:00 · 个人记录

排列数 A_n^m/P_n^m

long long A(long long m,long long n,long long mod){
    long long ans=1;
    for(long long i=n-m+1;i<=n;i++)
        ans=ans*i%mod;
    return ans;
}

时间复杂度 O(n)。

组合数 C_n^m

暴力

long long C(long long m,long long n,long long mod){
    m=min(m,n-m); 
    long long ans=1;
    for(long long i=n-m+1;i<=n;i++)
        ans=ans*i;
    for(int i=1;i<=m;i++)
        ans/=i; 
    return ans;
}

时间复杂度 O(n)。

递推

通过递推求出 C_1^1\sim C_n^m。

long long C[N][N]; 
void C_init(long long m,long long n,long long mod){
    for(int i=1;i<=n;i++)
        C[1][i]=i;
    for(int i=2;i<=m;i++)
        for(int j=i;j<=n;j++)
            if(i^j)
                C[i][j]=(C[i][j-1]+C[i-1][j-1])%mod;
            else
                C[i][j]=1;
}

预处理 O(nm)，查询 O(1)。

预处理阶乘及其逆元

m,n 同阶

预处理阶乘 jc 及其逆元 jc\_inv，通过公式求出组合数。

需要乘法逆元。

long long jc[N],jc_inv[N],mod;
void C_init(long long n){
    jc[0]=jc[1]=1%mod;
    for(long long i=2;i<=n;i++)
        jc[i]=(jc[i-1]*i%mod);
    for(long long i=1;i<=n;i++)
        jc_inv[i]=qni_fm(jc[i],mod);
}
long long C(long long m,long long n){
    return jc[n]*jc_inv[m]%mod*jc_inv[n-m]%mod;
}

预处理 O(\max(n,m)\log mod)，查询 O(1)。

m 特小，n 特大

需要乘法逆元。

long long inv[N],mod;
void C_init(int maxm){
    for(int i=1;i<=maxm;i++)
        inv[i]==qni_fm(i,mod);
}
long long C(long long m,long long n){
    if(m<0||n<0||m>n)
        return 0;
    n%=mod;
    if(!n||!m)
        return 1;
    long long ans=1;
    for(int i=n;i>n-m;i--)
        ans=ans*i%mod;
    for(int i=1;i<=m;i++)
        ans=ans*inv[i]%mod;
    return ans;
}

预处理 O(m\log mod)，查询 O(mod)。

利用 \text{Lucas} 定理

需要前面任何一种组合数求法 C_n^m。

long long LC(long long m,long long n,long long mod){
    if(!m)
        return 1;
    return LC(m/mod,n/mod,mod)*C(m%mod,n%mod,mod)%mod;
}

多重集的排列数 MA_n^m/MP_n^m

需要乘法逆元。

long long jc[N],jc_inv[N],mod;
void MA_init(long long n){
    jc[0]=jc[1]=1%mod;
    for(long long i=2;i<=n;i++)
        jc[i]=(jc[i-1]*i%mod);
    for(long long i=1;i<=n;i++)
        jc_inv[i]=qni_fm(jc[i],mod);
}
long long MA(long long m,long long k,long long *n){
    long long ans=jc[m];
    for(int i=1;i<=k;i++)
        ans=ans*jc_inv[n[i]]%mod;
    return ans;
}

预处理 O(n\log mod)，查询 O(k)。

多重集的组合数 MC_n^m

需要前面 m 特小，n 特大的预处理阶乘及其逆元的求组合数算法。

long long MC(int k,long long r,long long mod,long long *a){
    long long ans=0,t;
    int p;
    C_init(K);
    for(int x=0;x<(1<<k);x++)
        if(!x)
            ans=(ans+C(k-1,k+r-1))%mod;
        else{
            t=k+r;
            p=0;
            for(int i=0;i<k;i++)
                if((x>>i)&1)
                    p++,t-=a[i+1];
            t-=p+1;
            ans=(ans+(p&1?-1:1)*C(k-1,t))%mod;
        }
    return (ans+mod)%mod;
}

时间复杂度 O(k\times2^k)。

Catalan 数列

需要前面任何一种组合数求法 C_n^m 和乘法逆元。

long long Catalan(long long n,long long mod){
    return C(n,2*n,mod)*qni_fm(n+1,mod);
}