Combination

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1475 字

t组数据，每组给出n和m，求C对10007取

一本通
练习

正文

/*
原题：T1656「一本通 6.6 练习 5」Combination
题意：t 组数据，每组给出 n 和 m，求 C(n,m) 对 10007 取模的值。
思路：10007 是素数，直接用 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)
易错点：1) 预处理阶乘只需到 p-1，因为 Lucas 每步都把下标降到 p 以内；
2) m>n 时答案为 0，Lucas 过程中某一位出现 m_i>n_i 同样返回 0；
3) p 相同时阶乘表复用，不要每组重复计算。
*/
#include <bits/stdc++.h>
using namespace std;
const long long MOD=10007;
long long qpow(long long a,long long n){
    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;
void prepare(){
    fact.assign(MOD,1);
    for(long long i=1;i<MOD;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
    ifact.assign(MOD,1);
    ifact[MOD-1]=qpow(fact[MOD-1],MOD-2);
    for(long long i=MOD-2;i>=0;i--){
        ifact[i]=ifact[i+1]*(i+1)%MOD;
    }
}
long long combSmall(long long n,long long m){
    if(m<0 || m>n){
        return 0;
    }
    return fact[n]*ifact[m]%MOD*ifact[n-m]%MOD;
}
long long lucas(long long n,long long m){
    if(m<0 || m>n){
        return 0;
    }
    long long res=1;
    while(n>0 || m>0){
        res=res*combSmall(n%MOD,m%MOD)%MOD;
        n/=MOD;
        m/=MOD;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    prepare();
    int t;
    cin>>t;
    while(t--){
        long long n,m;
        cin>>n>>m;
        cout<<lucas(n,m)<<"\n";
    }
    return 0;
}

Combination

正文

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