C++

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<=109,m<=104,m<p<109,p是质数)。

【输出格式】

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

【样例输入】

  2

  5 2 3

  5 2 61

【样例输出】

  1

  10

 

分析

可以看到题目中的数据范围1<=m<=n<=109,m<=104,m<p<109,(再结合这是一道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*n1(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

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

 


作者:九城。,发布于:2019/08/14
原文:https://www.cnblogs.com/ninecities/p/11344994.html