我今天复习阶乘逆元的时候点开之前写的Lucas板题代码复习，结果越看越不对劲。

错误代码（求阶乘逆元的部分假了）：

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define M 100005
using namespace std;
ll n,m,p,a[M],b[M];
void pre();
ll lucas(ll,ll),C(ll,ll),ksm(ll,ll),f(ll);
signed main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&m,&p);
        pre();
        printf("%lld\n",f(lucas(n+m,m)));
    }
    return 0;
}
ll f(ll a){ return a%p;}
void pre(){
    a[0]=b[0]=a[1]=b[1]=1;
    for(int i=2;i<=p;i++) a[i]=f(a[i-1]*i);
    b[p-1]=f(ksm(p-1,p-2));
    for(int i=p-2;i>1;i--) b[i]=f(b[i+1]*(i+1));
}
ll ksm(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=f(ans*a);
        a=f(a*a),b>>=1;
    }
    return f(ans);
}
ll C(ll n,ll m){
    if(n<m) return 0;
    return f(f(a[n])*f(f(b[m])*f(b[n-m])));
}
ll lucas(ll n,ll m){
    if(!m) return 1;
    return f(f(C(n%p,m%p))*f(lucas(n/p,m/p)));
}

正确代码：

#include<bits/stdc++.h>
#define ll long long
#define M 100005
using namespace std;
ll t,n,m,p,a[M],b[M];
ll f(ll a){ return a%p;}
void pre();
ll ksm(ll,ll),c(ll,ll),lucas(ll,ll);
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&m,&p);
        pre();
        printf("%lld\n",f(lucas(n+m,n)));
    }
    return 0;
}
void pre(){
    a[1]=b[1]=a[0]=b[0]=1;
    for(int i=2;i<p;i++) a[i]=f(a[i-1]*i);
    b[p-1]=ksm(a[p-1],p-2);
    for(int i=p-2;i;i--) b[i]=f(b[i+1]*(i+1));
}
ll ksm(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=f(ans*a);
        b>>=1,a=f(a*a);
    }
    return f(ans);
}
ll c(ll n,ll m){
    if(n<m) return 0;
    return f(f(a[n]*b[m])*b[n-m]);
}
ll lucas(ll n,ll m){
    if(!m) return 1;
    return f(c(n%p,m%p)*lucas(n/p,m/p));
}

两份代码的区别在于这里

正确的阶乘逆元：

void pre(){
    a[1]=b[1]=a[0]=b[0]=1;
    for(int i=2;i<p;i++) a[i]=f(a[i-1]*i);
    b[p-1]=ksm(a[p-1],p-2);
    for(int i=p-2;i;i--) b[i]=f(b[i+1]*(i+1));
}

原先的假阶乘逆元：

void pre(){
    a[0]=b[0]=a[1]=b[1]=1;
    for(int i=2;i<=p;i++) a[i]=f(a[i-1]*i);
    b[p-1]=f(ksm(p-1,p-2));
    for(int i=p-2;i>1;i--) b[i]=f(b[i+1]*(i+1));
}

更确切地说，区别仅在于这里：

错误：

	b[p-1]=f(ksm(p-1,p-2));

正确：

    b[p-1]=ksm(a[p-1],p-2);

但是十分神奇的是，两份代码均通过了Lucas板题。

正确代码测试结果

假做法测试结果

这个到底是因为数据太水了，还是我自己对阶乘逆元的理解不到位，本质上这两种阶乘逆元的求法是相同的嘞？QwQ