Advertisement
Alex_tz307

NCK

Jan 26th, 2021
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.62 KB | None | 0 0
  1. const int mod = 666013;
  2.  
  3. int invers(int x) {
  4.     int exp = mod - 2, ans = 1;
  5.     while(exp) {
  6.         if(exp & 1)
  7.             ans = ans * x % mod;
  8.         x = x * x % mod;
  9.         exp >>= 1;
  10.     }
  11.     return ans;
  12. }
  13.  
  14. int nck(int N, int K) {
  15.     if(N < K)
  16.         return 0;
  17.     int st = 1, dr = N, other = K;
  18.     if(K < N - K) {
  19.         st = N - K + 1;
  20.         other = K;
  21.     }
  22.     else {
  23.         st = K + 1;
  24.         other = N - K;
  25.     }
  26.     int ans = 1;
  27.     for(int i = st; i <= dr; ++i)
  28.         ans = ans * i % mod;
  29.     int other_p = 1;
  30.     for(int i = 1; i <= other; ++i)
  31.         other_p = other_p * i % mod;
  32.     ans = ans * invers(other_p) % mod;
  33.     return ans;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement