组合数模板

逆元

• 定义: 当x * y≡1(mod p)，y就是x在mod p下的逆元

• 应用: a/b≡a * x(mod p)，x就是a的乘法逆元
  我们可以将a/b≡a * x(mod p)这个式子化简，两边同乘b-->a≡a * b * x(mod p)-->b * x≡1(mod p)
  又有费马小定理可知，b^(n-1)≡1(mod p)，所以x为b^{(p-2),所以逆元就是b}(p-2)

快速幂求逆元

就是根据b^(p-2)这个公式

int qsm(int x,int y){
  int res=1;
  while(y){
    if(y&1) res=(res*x)%p;
    y>>=1;
    x=(x*x)%p;
  }
  return res;
}

cout<<qsm(b,p-2);

组合数模板

ll qsm(ll x,ll y,ll p){
  ll ans=1;
  while(y){
    if(y&1) ans=(ans*x)%p;
    y>>=1;
    x=(x*x)%p;
  }
  return ans;
}
void init(){
  fact[0]=infact[0]=1;
  for(ll i=1;i<N;i++){
     fact[i]=fact[i-1]*i%mod;
     infact[i]=infact[i-1]*qsm(i,mod-2,mod)%mod;
  }
}
/*void init(){//两种写法，区别在于infact的求法，一个是每一次跑一遍快速幂，一个是智跑一次然后倒着跑，建议第二种
    fact[0]=1;
    for(ll i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
    infact[N-1]=qsm(fact[N-1],mod-2)%mod;
    for(ll i=N-1;i>=1;i--) infact[i-1]=infact[i]*i%mod;
    
}*/
ll solve(ll x,ll y){
  return fact[x]*infact[y]%mod*infact[x-y]%mod;
}