[模板] Lucas 逆元 快速幂模板

2019-04-13 21:25发布

站内文章 / 模拟电子
10597 0 1649
  • 一般情况下，当Mod较小，组合数较大时用Lucas求组合数，当Mod较大组合数较小时用逆元求组合数
/* 逆元定义：x为a的乘法逆元，(b/a) (mod Mod) = (b * x) (mod Mod) x表示a的逆元。并且 a*x ≡ 1 (mod Mod ) 注意：只有当a与Mod互质的时候才存在逆元 以下两种写法都必须要求MOD为素数 */ typedef long long ll; const int Mod=110119; ll invs[Mod+50]; ll fac[Mod+50]; //1 预处理 void initInv(int Mod){ invs[1]=1; for (int i=2;i//2 直接求 ll inv(int a,int mod){ return(a==1?1:inv(mod%a,mod)*(mod-mod/a)%mod); } //3 inv(x)=x^(mod-2) ll qPow(ll x,ll n,ll mod){ ll ret=1; while(n){ if (n&1) ret=(ret*x)%mod; x=(x*x)%mod; n>>=1; } return ret; //x^n%mod } void initFac(int Mod){ //n! fac[0]=1; for(int i=1;i<=Mod;i++){ fac[i]=fac[i-1]*i%Mod; } } ll lucas(ll n,ll k,ll mod){ //C_n^k%mod if (n<0 || k<0 || k>n) return 0; ll ret=1; while(n && k){ ll np=n%mod,kp=k%mod; if (npreturn 0; ret=(ret*fac[np]%mod)*invs[fac[kp]*fac[np-kp]%mod]%mod; // ret=(ret*fac[np]%mod)*inv(fac[kp]*fac[np-kp]%mod,mod)%mod; // ret=(ret*fac[np]%mod)*qPow(fac[kp]*fac[np-kp]%mod,mod-2,mod)%mod; n/=mod; k/=mod; } return ret; } //调用 //initFac(Mod); //initInv(Mod); //return lucas(n,m,Mod);

热门文章