Lucas定理模板

一本通上不是很懂，所以自己查资料做了个总结。

lucas定理：若p是质数，则对于任意整数1<=m<=n，有：

　　c(n,m)%p=c(n%p,m%p)*c(n/p,m/p)%p

也就是把n和m表示成p进制数，对p进制下的每一位分别计算组合数，最后再乘起来。

最后一句话可能难以理解，实际上联想到平常求一个十进制数的二进制数，也是对十进制数进行不断取模，由除以二的余数得到二进制数，所以对于lucas定理也差不多是一个道理。

由于计算过程中不断地取模，同时事实上c(n/p,m/p)仍可以拆分，所以主要用于组合数中n,m较大时的问题中。

 

模板题

【问题描述】

　　给出组合数c(n,m)，表示从n个元素中选出m个元素的方案数。例如c(5,2)=10，c(4,2)。可是当n,m比较大的时候，c(n,m)很大！于是小波希望你输出c(n,m)mod p的值。

【输入格式】

　　输入数据第一行是一个正整数t，表示数据组数(t<=100)。

　　接下来是t组数据，每组数据有3个正整数n,m,p(1<=m<=n<=10⁹,m<=10⁴,m<p<10⁹,p是质数)。

【输出格式】

　　对于每组数据，输出一个正整数，表示c(n,m)mod p的结果。

【样例输入】

　　2

　　5 2 3

　　5 2 61

【样例输出】

　　1

　　10

 

分析

可以看到题目中的数据范围1<=m<=n<=10⁹,m<=10⁴,m<p<10⁹，（再结合这是一道lucas模板题），所以可以很轻松的分析出这道题用普通递推是过不了的，所以就要用到我们的lucas定理哒。

首先根据前文的分析可以打出主函数和lucas的函数部分。

主函数：

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&p);
        printf("%d\n",lucas(n,m));
    }
    
    return 0;
}

lucas：

ll lucas(ll n,ll m)//注意本题数据范围过大要开long long
{
    if(!m)    return 1;//一个很容易理解的特判 
    else return (c(n%p,m%p)*lucas(n/p,m/p))%p;
} 

接下来主要分析c(n%p,m%p)的求解。

我们知道c(n,m)=n!/[m!(n-m)!]=[n*(n-1)*...*(n-m+1)]/m!，也就是说，只要我们能够分别求解[n*(n-1)*...*(n-m+1)]和m!，那么就可以得到问题的答案。但是！别忘了还有取模计算！当涉及取模运算的计算中，如果有除法，不能直接除以一个数，而是变成乘以它的乘法逆元。（如果有不知道乘法逆元的朋友慢慢往后看应该能够意会的，或者可以问度娘）

（关于这句话个人理解是因为两数相除会有除不尽的情况，不方便取模。又因a*b%c=(a%c*b%c)%c，所以可求出乘法逆元。如有曲解烦请指出qwq)

这里主要介绍利用费马小定理求解乘法逆元

费马小定理：如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）

记住这句话！！！（p.s. a≡b(mod n)相当于a被n整除余数为b的意思）

 

先来继续前面的分析。当我们除以一个数n时，也就是乘上1/n，所以我们可以假设x为1/n关于模n的逆元，则有x≡1/n(mod p)，即x*n≡1(mod p)。看到这里可以发现这个式子有一半跟费马小定理一模一样！而通过题目已知p为质数（做题中大部分情况下p也都为质数），所以我们可以直接套用费马小定理！

得到：x*n=n^(p-1)，即x=n^(p-2)！

所以只要运用这个结论，再结合快速幂，就可以轻松求解哒。

求解c(n%p,m%p)部分：

 

ll c(ll n,ll m)
{
    if(m>n)    return 0;
    ll a=1,b=1;
    for(ll i=n-m+1;i<=n;++i)
        a=a*i%p;
    for(ll i=2;i<=m;++i)
        b=b*i%p;
    return a*quickpow(b,p-2)%p;
}

 

费马小定理和快速幂求解乘法逆元部分：

ll quickpow(ll a,ll b)
{
    ll s=1;
    while(b)
    {
        if(b&1)    s=s*a%p;
        a=a*a%p;
        b>>=1;
    }
    
    return s;
}

所以这道其实很简单的模板题就能被我们轻松掌握啦。

完整代码：

#include<iostream>
#include<cstdio>
#define ll long long

using namespace std;
ll p; 

ll quickpow(ll a,ll b)
{
    ll s=1;
    while(b)
    {
        if(b&1)    s=s*a%p;
        a=a*a%p;
        b>>=1;
    }
    
    return s;
}

ll c(ll n,ll m)
{
    if(m>n)    return 0;
    ll a=1,b=1;
    for(ll i=n-m+1;i<=n;++i)
        a=a*i%p;
    for(ll i=2;i<=m;++i)
        b=b*i%p;
    return a*quickpow(b,p-2)%p;
}

ll lucas(ll n,ll m)
{
    if(!m)    return 1;
    else return (c(n%p,m%p)*lucas(n/p,m/p))%p;
} 

int main()
{
    ll n,m;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&p);
        printf("%d\n",lucas(n,m));
    }
    
    return 0;
}

希望能对大家对自己有一定的帮助吧qwq

部分资料源于度娘，如有错误或侵权烦请指出~