# 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
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