paradox64ce

nCr with mod

Jan 26th, 2021
747
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ll power(ll x, ll y)
  2. {
  3.     ll res = 1;
  4.  
  5.     while (y > 0)
  6.     {
  7.         if (y & 1)
  8.             res = (res * x) % MOD;
  9.         y = y >> 1;
  10.         x = (x * x) % MOD;
  11.     }
  12.     return res;
  13. }
  14.  
  15. ll modInv(ll x)
  16. {
  17.     return power(x, MOD - 2);
  18. }
  19.  
  20. ll C(ll n, ll r)
  21. {
  22.     ll ans = fact[n] % MOD;
  23.     ans = (ans * modInv(fact[n - r])) % MOD;
  24.     ans = (ans * modInv(fact[r])) % MOD;
  25.     return ans;
  26. }
RAW Paste Data