组合

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1538 字
T组数据，每组给出n,m,p，求Cmodp的
一本通
例
正文

/*
原题：T1650「一本通 6.6 例 3」组合
题意：T 组数据，每组给出 n,m,p，求 C(n,m) mod p 的值，其中 p 为素数。
思路：用 Lucas 定理：C(n,m) mod p = Π C(n_i,m_i) mod p，
其中 n_i、m_i 是 n、m 在 p 进制下的各位；预处理 p 以内的阶乘与其逆元即可 O(log_p n) 求出。
复杂度：每组 O(p+log_p n)，空间 O(p)
易错点：1) n<m 时答案为 0，Lucas 里表现为某一位 m_i>n_i，直接返回 0；
2) 阶乘数组要开到 p-1（含 p-1），逆元用费马小定理快速幂求；
3) p 相同时阶乘表可复用，不必每组重算。
*/
#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a,long long n,long long mod){
    long long r=1;
    a%=mod;
    while(n>0){
        if(n&1){
            r=r*a%mod;
        }
        a=a*a%mod;
        n>>=1;
    }
    return r;
}
vector<long long> fact,ifact;
long long curMod=-1;
void prepare(long long p){
    fact.assign(p,1);
    for(long long i=1;i<p;i++){
        fact[i]=fact[i-1]*i%p;
    }
    ifact.assign(p,1);
    ifact[p-1]=qpow(fact[p-1],p-2,p);
    for(long long i=p-2;i>=0;i--){
        ifact[i]=ifact[i+1]*(i+1)%p;
    }
}
long long smallC(long long n,long long m,long long p){
    if(m>n){
        return 0;
    }
    return fact[n]*ifact[m]%p*ifact[n-m]%p;
}
long long lucas(long long n,long long m,long long p){
    if(m<0 || m>n){
        return 0;
    }
    long long res=1;
    while(n>0 || m>0){
        res=res*smallC(n%p,m%p,p)%p;
        n/=p;
        m/=p;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        long long n,m,p;
        cin>>n>>m>>p;
        if(p!=curMod){
            prepare(p);
            curMod=p;
        }
        cout<<lucas(n,m,p)<<"\n";
    }
    return 0;
}
组合

正文

一本通·提高篇的其它内容
