Lucas定理

201929 • 2023年08月23日 01:33 • 1年前 • 编程日记 • 阅读(0) • 违法举报

Lucas定理：

主要是求$C_{n}^{m}$在模$p$情况下($mod \, p$)(一般$p$较小，而$n,m$较大的情况)

公式:

$ C_{n}^{m} ≡ C_{n \, mod \, p}^{m \, mod \, p} \times C_{n/p}^{m/p} (mod \, p) $

证明以后补吧

就以这题来说明具体解法：

题目

Luogu P3807 【模板】卢卡斯定理/Lucas 定理

Code:

//From:201929
#include<bits/stdc++.h>
#define L long long
using namespace std;
L pq[100005];
L n,m,mod;
L quick(L x,L y)//快速幂
{
    L ans=1;
    while(y)
    {
        if(y%2) ans=(ans*x)%mod;
        y>>=1;
        x=(x*x)%mod;
    }
    return ans;
}
L q(L x,L y)
{
    if(y>x) return 0;
    return (pq[x]*quick(pq[y],mod-2))%mod*quick(pq[x-y],mod-2)%mod;
    //pq[x]/pq[y]/pq[x-y]
    //逆元变成pq[x]*(pq[y]^(mod-2))*(pq[x-y]^(mod-2))
    //暴力求解C x,y的值
}
L lucas(L x,L y)
{
    if(y==0) return 1ll;
    return (lucas(x/mod,y/mod)*q(x%mod,y%mod))%mod;
}
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&m,&mod);
        pq[0]=1;
        for(int i=1;i<=mod;i++) pq[i]=(pq[i-1]*i)%mod;
        //预处理小情况（x<mod）的答案
        printf("%lld\n",lucas(n+m,m));
    }
    return 0;
}

文章来源地址https://uudwc.com/A/ZmpY1

原文地址:https://www.cnblogs.com/201929-whx/p/17606822.html

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请联系站长进行投诉反馈，一经查实，立即删除！