Lucas定理

定义

对于质数 \(p\)，有：$$\dbinom{n}{m} \mod p=\dbinom{n \mod p}{m \mod p} \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \mod p$$

由于 \(n \mod p\) 和 \(m \mod p\) 都比模数 \(p\) 小，可以预处理，而 \(\tbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\) 则可以再次调用 \(Lucas\) 定理求解。

时间复杂度：\(O(\log n)\)

意义

对于一般的组合数，我们有预处理 \(O(n)\) 和单次查询 \(O(1)\) 的阶乘算法，但是当 \(n\) 和 \(m\) 都特别大的时候，我们无法用数组来存那么多数的阶乘，于是使用牺牲时间换空间的方法。

\(Lucas\) 定理就是对于 \(n\) 和 \(m\) 特别大的时候，而模数 \(p\) 不是很大的时候，来求解组合数的算法。在求解过程中，发现只需要存 \(0 \sim p\) 的阶乘即可。但是单次查询的时间复杂度也由原来的 \(O(1)\) 变为 \(O(\log n)\)。

当然，当 \(n\) 和 \(m\) 以及 \(p\) 都非常大的时候，目前并没有更优的解法，只能用单次查询 \(O(n)\) 的暴力了。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e4;
const int mod=1e4+7;
LL f[N+5];
void init(){
    f[0]=1;
    for(int i=1;i<=N;i++){
        f[i]=f[i-1]*i%mod;
    }
}
LL qpow(LL a,LL b){
    LL ans=1%mod;a%=mod;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;b>>=1;
    }
    return ans;
}
LL C(LL n,LL m){
    if(n<m)return 0;
    return f[n]*qpow(f[m],mod-2)%mod*qpow(f[n-m],mod-2)%mod;
}
LL Lucas(LL n,LL m,LL p){
    if(!m)return 1;
    return C(n%p,m%p)*lucas(n/p,m/p,p)%p;
}
int main(){
    init();
    int t;scanf("%d",&t);
    while(t--){
        LL n,m;scanf("%lld%lld",&n,&m);
        printf("%lld\n",Lucas(n,m,mod));
    }
    return 0;
}