Niloy007

Combinations

May 11th, 2021
633
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define Niloy
  3. #define int int64_t
  4. #define mx (int) 1e6 + 123
  5. #define MOD (int) 1000003
  6. #define pb push_back
  7. #define pairs pair<int, int>
  8. #define vi vector<int>
  9. #define vb vector<bool>
  10. #define vii vector<pairs>
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define endl '\n'
  14. #define llu unsigned long long
  15. using namespace std;
  16. /* ----------------------------------------------------------------------------------- */
  17.  
  18. // Input/Output
  19. #define fastInput ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  20. #define all(x) x.begin(), x.end()
  21. #define square(a) (a * a)
  22. #define mem(a, b) memset(a, b, sizeof(a))
  23.  
  24. // Fractional Number
  25. #define fraction()        cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield);
  26.  
  27. // Modular Arithmatic
  28. inline void normal(int &a) { a %= MOD; (a < 0) && (a += MOD); }
  29. inline int modMul(int a, int b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
  30. inline int modAdd(int a, int b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
  31. inline int modSub(int a, int b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
  32. inline int modPow(int b, int p) { int r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
  33. inline int modInverse(int a) { return modPow(a, MOD-2); }
  34. inline int modDiv(int a, int b) { return modMul(a, modInverse(b)); }
  35.  
  36. // Direction Array
  37. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
  38. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  39.  
  40. // File I/O
  41. #define read(x)  freopen(x, "r", stdin);
  42. #define write(x) freopen(x, "w", stdout);
  43.  
  44. // Loops
  45. #define rep(i, a, n) for (int i = a; i < n; i++)
  46. #define REP(i, a, n) for (int i = a; i <= n; i++)
  47. #define rev(i, n, a) for (int i = n - 1; i >= a; i--)
  48. #define REV(i, n, a) for (int i = n; i >= a; i--)
  49.  
  50. /* ----------------------------------------------------------------------------------- */
  51.  
  52. #define Cases  cout << "Case " << ++Case << ": ";
  53. #define __test int tt; int Case=0; cin >> tt; while(tt--)
  54. #define showTime cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
  55.  
  56. #define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, m){cout<<A[i][j]<<"";}cout<<"\n";}cout<<"\n";}
  57. #define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
  58. #define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}
  59.  
  60. /* ----------------------------------------------------------------------------------- */
  61.  
  62. int gcd(int n, int m) { return m ? gcd(m, n % m) : n; }
  63. int lcm(int n, int m) { return n / gcd(n, m) * m; }
  64.  
  65. struct debugger {
  66.     typedef string::iterator si;
  67.     static void call(si it, si ed) {}
  68.     template<typename T, typename ... aT>
  69.     static void call(si it, si ed, T a, aT... rest) {
  70.         string b;
  71.         for(; *it!=','; ++it)
  72.             if(*it!=' ')
  73.                 b+=*it;
  74.         cout << b << "=" << a << " ";
  75.         call(++it, ed, rest...);
  76.     }
  77. };
  78.  
  79. /* ----------------------------------------------------------------------------------- */
  80. void input() {
  81. #ifdef Niloy
  82.     read("input.txt");  
  83.     write("output.txt");
  84. #endif
  85. }
  86.  
  87. /* ----------------------------------------------------------------------------------- */
  88.  
  89. int fact[mx];
  90. int invFact[mx];
  91.  
  92. void init() {
  93.     fact[0] = 1;
  94.     invFact[0] = 1;
  95.     int limit = 1e6;
  96.     REP(i, 1, limit) {
  97.         fact[i] = modMul(fact[i - 1], i);
  98.         invFact[i] = (modInverse(fact[i]) % MOD);
  99.     }
  100. }
  101.  
  102. void solve() {
  103.     int n, k;
  104.     cin >> n >> k;
  105.     int ans = modMul(modMul(fact[n], invFact[n - k]), invFact[k]);
  106.     cout << ans << endl;
  107. }
  108.  
  109. int32_t main() {
  110.     // input();
  111.     fastInput;
  112.     // solve();
  113.  
  114.     init();
  115.     __test {
  116.         Cases;
  117.         solve();
  118.     }
  119.  
  120.     // showTime;
  121.     return 0;
  122. }
  123.  
RAW Paste Data