乘法逆元费马小定理

``` //inv[i]=i^(mod-2) //逆元的含义：模mod意义下，1个数a如果有逆元x，那么除以a相当于乘以x。 #define ll long long ll inv[50010],fac[50010]; int mod=1e9+7; ll pow(int a,int b,int mod) { ll ans=0,base=a; while(b) { if(b&1)ans=base*a; b>>=1; base*=base; } return ans; } //计算组合数时需要用到阶乘的逆元，也可以做到O(n)递推 //inv[i]=inv[i+1]*(i+1)%mod for(int i=1;i<=n;i++)fac[i]=i*fac[i-1]%mod; inv[n]=pow(fac[n],mod-2,mod); for(int i=n-1;i;i--) inv[i]=(inv[i+1]*(i+1))%mod; ```