来自Perm排列计数的悲伤

 

lucas说过

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

于是乎

在好记的情况下没有搞原理证明

导致PermWA了一上午

ll pow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans%p;
}
ll C(int a,int b){
    if(a<b)return 0;
    if(b==0)return 1;
    return jc[a]*pow(jc[a-b]*jc[b]%p,p-2)%p;
}
ll lucas(int a,int b){
    if(b>a)return 0;
    if(b==0)return 1;
    if(a>p||b>p)return C(a%p,b%p)*lucas(a/p,b/p)%p;
    return C(a,b)%p;
}
        jc[0]=1;
    for(int i=1;i<=n;++i)jc[i]=jc[i-1]*1ll*i%p;    

注意事项：{

　　（1）能mod即mod

　　　　代码中主要为相乘运算

　　　　很容易爆long long

　　（2）特判：

　　　　m==0 return 1;

　　　　n<m return 0;

　　（3）lucas细节

　　　　只有当

　　　　n>mod||m>mod 才有lucas　　　　

}

最后

逆元建议线性推

本人太懒

拿了快速幂取模凑数