This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub SSRS-cp/cp_library
//Input: n, MOD //Output: C_n mod MOD //Time: O(1) long long modpow(long long a, long long b){ long long res = 1; while (b > 0){ if (b % 2 == 1) res = res * a % MOD; a = a * a % MOD; b = b / 2; } return res; } long long modinv(long long a){ return modpow(a, MOD - 2); } vector<long long> mf; long long modfact(long long n){ if (n < mf.size()){ return mf[n]; } else { if (mf.empty()) mf.push_back(1); long long res = mf.back(); for (int i = mf.size(); i <= n; i++){ res = res * i % MOD; mf.push_back(res); } return res; } } long long catalan_number(long long n){ long long res; res = modfact(n * 2); res = res * modinv(modfact(n + 1)) % MOD; res = res * modinv(modfact(n)) % MOD; return res; }
#line 1 "old_Math/Catalan_Number.cpp" //Input: n, MOD //Output: C_n mod MOD //Time: O(1) long long modpow(long long a, long long b){ long long res = 1; while (b > 0){ if (b % 2 == 1) res = res * a % MOD; a = a * a % MOD; b = b / 2; } return res; } long long modinv(long long a){ return modpow(a, MOD - 2); } vector<long long> mf; long long modfact(long long n){ if (n < mf.size()){ return mf[n]; } else { if (mf.empty()) mf.push_back(1); long long res = mf.back(); for (int i = mf.size(); i <= n; i++){ res = res * i % MOD; mf.push_back(res); } return res; } } long long catalan_number(long long n){ long long res; res = modfact(n * 2); res = res * modinv(modfact(n + 1)) % MOD; res = res * modinv(modfact(n)) % MOD; return res; }