조합

1. my_pow 부분 2. 하는 이유 3. % 숫자가 큰 경우에 이렇게 실행 4. 어떤 규칙이 있음

#include<iostream> using namespace std; #define DIV 1234567891 typedef long long ll; ll fact[1000010]; ll my_pow(ll base, ll exp) { ll res = 1; while (exp) { if (exp & 1) { res *= base; res %= DIV; } exp >>= 1; base *= base; base %= DIV; } res %= DIV; return res; } int main(int argc, char** argv) { freopen("input.txt", "r", stdin); int test_case; int T; fact[1] = 1; for (ll i = 2; i <= 1000001; i++) { fact[i] = (fact[i - 1] * i) % DIV; // factorial 미리 계산해두기 } cin >> T; for (test_case = 1; test_case <= T; ++test_case) { ll ans; int N, R; cin >> N >> R; ll tmp = (fact[R] * fact[N - R]) % DIV; ans = (fact[N] * my_pow(tmp, DIV - 2)) % DIV; cout << "#" << test_case << " " << ans << "\n"; } return 0; }