来自perm排列计数的悲伤
lucas说过
c(n,m)%p=c(n%p,m%p)*c(n/p,m/p)%p
于是乎
在好记的情况下没有搞原理证明
导致permwa了一上午
1 ll pow(ll a,ll b){ 2 ll ans=1; 3 while(b){ 4 if(b&1)ans=(ans*a)%p; 5 a=(a*a)%p; 6 b>>=1; 7 } 8 return ans%p; 9 } 10 ll c(int a,int b){ 11 if(a<b)return 0; 12 if(b==0)return 1; 13 return jc[a]*pow(jc[a-b]*jc[b]%p,p-2)%p; 14 } 15 ll lucas(int a,int b){ 16 if(b>a)return 0; 17 if(b==0)return 1; 18 if(a>p||b>p)return c(a%p,b%p)*lucas(a/p,b/p)%p; 19 return c(a,b)%p; 20 } 21 jc[0]=1; 22 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
}
最后
逆元建议线性推
本人太懒
拿了快速幂取模凑数
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/602843.html