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;
}

526互联

Lucas定理及其扩展

Lucas定理

定义

意义

Code