P3807【模板】卢卡斯定理

· · 题解

题解大部分都是递归实现的，给出一种非递归的形式
话说上课老师讲的时候没给代码，然后自己些就写成了这样

对于质数p给出卢卡斯定理：

\tbinom{n}{m}=\tbinom{n \bmod p}{m \bmod p}\tbinom{\lfloor \frac{n}{p}\rfloor}{\lfloor \frac{m}{p} \rfloor}\pmod p

其实它还有另一种形式，虽然本质上没啥区别：

\tbinom{n}{m}=\prod_{i=1}^k \tbinom{a_i}{b_i} \pmod p

其中，a,b分别为n,m的p进制下的每一位，k是它们位数的较大值，当然如果有数不足k位，要补前导0

来证明一下
其实证明方法也是看了别人blog才知道的
设s=\lfloor \dfrac{n}{p}\rfloor,t=\lfloor \dfrac{m}{p}\rfloor
则有q,w使得n=sp+q,m=tp+w
再考虑一个二项式：

(1+x)^n=((1+x)^p)^s(1+x)^q

 
先由费马小定理推个结论：

x^p\equiv x\pmod p \Rightarrow (x^p+1)\equiv (x+1)\pmod p (x+1)^p\equiv (x+1)\pmod p

所以：

(x+1)^p\equiv (x^p+1)\pmod p

 
把这个结论带进去：

(1+x)^n\equiv (1+x^p)^s(1+x)^q \pmod p

再由二项式定理把右边展开

(1+x)^n\equiv \sum_{i=1}^s \tbinom{s}{i}x^{pi}\cdot \sum_{j=1}^q \tbinom{q}{j}x^j

同样我们可以把左边展开：

(1+x)^n=\sum_{i=1}^{sp+q}\tbinom{sp+q}{i}x^i

然后我们可以发现，左右两遍都有x^{tp+w}次项（当然，这是在m\leq n的情形下，如果m>n结果就是0，不用考虑了）
比较一下它们的系数
左边：\tbinom{sp+q}{tp+w}x^{tp+w}
右边：\tbinom{s}{t}x^{tp}\cdot \tbinom{q}{w}x^w
这边要说明一下，不会出现别的次数组合，比如(t-1)p和(w+p)，因为w,q<p
所以：\tbinom{sp+q}{tp+w}\equiv \tbinom{s}{t}\tbinom{q}{w}\pmod p
即：

\tbinom{n}{m}\equiv\tbinom{n \bmod p}{m \bmod p}\tbinom{\lfloor \frac{n}{p}\rfloor}{\lfloor \frac{m}{p} \rfloor}\pmod p

然后把\tbinom{\lfloor \frac{n}{p}\rfloor}{\lfloor \frac{m}{p} \rfloor}这一项不断展开，其实就变为了那种非递归形式

好了，我们终于得到了这个定理
那写代码就简单了，将n,m转化为p进制
预处理出阶乘数组，和阶乘的逆元数组
然后对于这p进制的每一位直接套组合数公式就行了
然而代码似乎没有递归的好写
另外一共5个点，我错了三遍下载了三个数据来调
那么说一下踩得坑，首先主函数for循环里的特判一定要有，避免出现数组下标变成负数，或者使用0的逆元的情况
还有多测时前导0的位置一定要清零 

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<stack>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
    int x=0,y=1;
    char c=std::getchar();
    while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
    return y?x:-x;
}
int n,m,p;
LL fac[200006],g[200006];
int a[100006],b[100006];
inline LL power(LL x,LL y){
    reg LL ans=1;
    while(y){
        if(y&1) ans=(1ll*ans*x)%p;
        y>>=1;x=(x*x*1ll)%p;
    }
    return ans;
}
std::stack<int>s;
inline void pre(){//预处理函数
    a[0]=b[0]=0;
    while(n){
        s.push(n%p);n/=p;
    }
    while(!s.empty()) a[++a[0]]=s.top(),s.pop();
    int tmp=0;
    while(m){
        tmp++;
        s.push(m%p);m/=p;
    }
    while(b[0]+tmp<a[0]) b[++b[0]]=0;//前导零的位置一定要清零 
    while(!s.empty()) b[++b[0]]=s.top(),s.pop();
    fac[0]=1;
    for(reg int i=1;i<p;i++) fac[i]=(1ll*fac[i-1]*i)%p;
    g[p-1]=power(fac[p-1],p-2);
    for(reg int i=p-2;i;i--) g[i]=(1ll*g[i+1]*(i+1))%p;
}
int main(){int t=read();while(t--){
    n=read();m=read();p=read();
    n+=m;m=n-m;
//  std::memset(a,0,sizeof a);std::memset(b,0,sizeof b);
    pre();
//      for(reg int i=1;i<=a[0];i++) std::printf("%d ",a[i]);EN;
//      for(reg int i=1;i<=b[0];i++) std::printf("%d ",b[i]);EN;
//      for(reg int i=0;i<p;i++) std::printf("%d ",fac[i]);EN;
//      for(reg int i=0;i<p;i++) std::printf("%d ",g[i]);EN;
    LL ans=1;
//      std::printf("%d %d\n",a[0],b[0]);
    for(reg int i=1;i<=a[0];i++){
        if(!b[i]) continue;
        if(a[i]<b[i]){ans=0;break;}
        if(a[i]==b[i]) continue;
        ans=(1ll*ans*fac[a[i]])%p;
        ans=(1ll*ans*g[b[i]])%p;
        ans=(1ll*ans*g[a[i]-b[i]])%p;
    }
    std::printf("%lld\n",ans);
}
    return 0;
}