Lucas定理

· · 个人记录

卢卡斯定理

卢卡斯定理

卢卡斯定理是求C^{m}_{n}的快速方法。

证明

$\therefore$ 定理成立 具体浏览某大佬的证明。 #### 公式 $C^m_n\equiv C^{\lfloor \frac{m}{p} \rfloor}_{\lfloor \frac{n}{p} \rfloor}\times C^{m\ mod\ p}_{n\ mod\ p}\ \color{red}(mod\ p)

实现

组合操作：

int c(int m,int n,int p){
    if (n<m) return 0;//上面比下面大，当然输出0
    if (m>=p || n>=p) return c(m/p,n/p,c)*c(m%p,n%p,p);//公式的直接调用
    if (m==0 || n==0) return 1;//有一个是0，就输出1
    return fact[n]*invfact[m]%p*invfact[n-m]%p;
}

最后一句话的意思是：

return\ n!\times\prod^{m}_{i=1}inv(i)\ mod \ p\times\prod^{n-m}_{i=1}inv(i)\ mod \ p $inv$的递推求法 ``` inv[1]=1; for (int i=2;i<=p;i++) inv[i]=(p-p/i)*inv[p%i]%p; ``` $invfact$是$inv$的累乘 ``` invfact[1]=inv[1]; for (int i=2;i<=p;i++) invfact[i]=invfact[i-1]*inv[i]%p; ``` 当然可以直接对$inv$数组动手 ``` for (int i=2;i<=p;i++) inv[i]=inv[i-1]*inv[i]%p; ``` 阶乘$fact 
fact[0]=fact[1]=1;
for (int i=2;i<=p;i++) fact[i]=fact[i-1]*i%p;

就这样完成了！

求C^m_n\ mod\ p的值只需要调用C(m,n,p)即可。

完整代码

P3807模板题

注意，这道模板题求的是C^m_{m+n}\ mod\ p！

#include <bits/stdc++.h>
#define N 100001
using namespace std;
#define LL long long
LL f[N],inv[N];
inline LL C(int m,int n,int p) {
    if (n<m) return 0;
    if (m>=p || n>=p) return C(m/p,n/p,p)*C(m%p,n%p,p)%p;
    if (m==0 || n==0) return 1;
    return f[n]*inv[m]%p*inv[n-m]%p;
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--){
        int m,n,p;
        scanf("%d %d %d",&n,&m,&p);
        n+=m;f[0]=inv[0]=f[1]=inv[1]=1;
        for (int i=2;i<=p;i++) f[i]=f[i-1]*i%p;
        for (int i=2;i<=p;i++) inv[i]=(p-p/i)*inv[p%i]%p;
        for (int i=2;i<=p;i++) inv[i]=inv[i-1]*inv[i]%p; 
        printf("%lld\n",C(m,n,p));
    }
    return 0;
}