题解 P3807 【【模板】卢卡斯定理】

· · 题解

如何不用lucas

这个模板的n,m都是1e5，显然不用lucas也可以做(lucas复杂度O(log_{p}(n)*p)，接近于O(p)，暴力做复杂度是O(n))

然后就是暴力如何实现的问题（前面有人写了质因数分解的做法然而还可以再简单一点）

前置知识：快速幂，费马小定理求逆元or线性筛逆元，不会的到这里学乘法逆元题解（来做lucas的都会吧）

直接用逆元求\dfrac{(n+m)!}{n!*m!}，稍微化简一下就是\dfrac{\prod_{i=n}^mi}{m!}

上面的直接乘起来就好了（当然要取模），然后看下面的，要求1-m的逆元，可以线性筛逆元（这个题费马小定理也能过）之后乘上去就好了

交上去发现全部WA并且都是非0的输出0

思考一下为什么：(n+m)!中有p的倍数，但是\dfrac{(n+m)!}{n!*m!}化简后没有p这个因数；上面的做法在计算的时候遇到p的倍数直接就模成0了

解决方法：每乘到一个数，先把它除p直到不是p的倍数，再算就不会出0了

然后这样会把答案是0的算成不是0，记录一下上面和下面各有多少个因子p然后如果相等，答案就是算出的答案，如果不相等，答案就是0，正确性显然（相等就能全部余约掉，否则不能）

还有一些坑点在注释里

代码（费马小定理）

#include<iostream>
#include<cstdio>
#define ni(x) power(x,md-2)
using namespace std;

char rc;
void read(long long &x)
{
    x=0;rc=getchar();
    while(rc<'0'||rc>'9')
      rc=getchar();
    while(rc>='0'&&rc<='9')
      x=x*10+rc-'0',rc=getchar();
}

long long n,m,md,t,T,i,ans;//md就是题目的p 

long long power(long long a,long long n)
{
    long long ans=1;
    while(n)
    {
        if(n&1)
          ans=(ans*a)%md;
        a=(a*a)%md;
        n>>=1;
    }
    return ans;
}

int cnt;
long long check(long long x,long long detla)//除掉因子p 
{
    while(x%md==0)
      x/=md,cnt+=detla;//算分子的时候detle每次+1，分母每次-1 
    return x;
}

int main()
{
    cin>>t;
    for(T=1;T<=t;T++)
    {
        cin>>n>>m>>md;cnt=0;
        ans=1;
        for(i=n+1;i<=n+m;i++)
          ans=(ans*check(i,1))%md;
        for(i=2;i<=m;i++)
          ans=(ans*ni(check(i,-1)))%md;
        cout<<(cnt==0?ans:0)<<endl;
    }
    return 0;
}

代码（线性筛）

#include<iostream>
#include<cstdio>
using namespace std;

char rc;
void read(long long &x)
{
    x=0;rc=getchar();
    while(rc<'0'||rc>'9')
      rc=getchar();
    while(rc>='0'&&rc<='9')
      x=x*10+rc-'0',rc=getchar();
}

long long n,m,md,t,T,i,ans,ni[200005];//md就是题目中的p 

int cnt;
long long check(long long x,long long detla)//除掉因子p 
{
    while(x%md==0)
      x/=md,cnt+=detla;//算分子的时候detle每次+1,分母每次-1 
    return x;
}

int main()
{
    cin>>t;
    for(T=1;T<=t;T++)
    {
        cin>>n>>m>>md;cnt=0;
        ni[1]=1;//这三行是线性筛逆元 
        for(i=2;i<md;i++)
          ni[i]=((-(md/i)*ni[md%i])%md+md)%md;//注意要 求正数 
        ans=1;
        for(i=n+1;i<=n+m;i++)
          ans=(ans*check(i,1))%md;
        for(i=2;i<=m;i++)
          ans=(ans*ni[check(i,-1)%md])%md;//线性筛逆元只能筛到p-1，大于p的m逆元等于m%p的逆元 
        cout<<(cnt==0?ans:0)<<endl;
    }
    return 0;
}