Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #define ull unsigned long long
- using namespace std;
- ull OMI(ull a, ull b, ull s0 = 1, ull s1 = 0) {
- return b==0? s0: OMI(b, a%b, s1, s0 - s1*(a/b));
- }
- ull binomialCoeff(ull n, ull k) {
- ull res = 1;
- if (k > n - k)
- k = n - k;
- for (ull i = 0; i < k; ++i) {
- res *= (n - i);
- res /= (i + 1);
- //ull temp = OMI(i + 1, 1000000007);
- //res *= (temp < 0) ? temp + 1000000007 : temp;
- }
- return res;
- }
- ull catalan(ull n) {
- ull c = binomialCoeff(2*n, n);
- ull temp = OMI(n + 1, 1000000007);
- //res *= (temp < 0) ? temp + 1000000007 : temp;
- //return c/(n+1);
- return c * ((temp < 0) ? temp + 1000000007 : temp);
- }
- int main() {
- ull n;
- cin >> n;
- if(n == 1) {
- cout << 1;
- return 0;
- }
- cout << catalan(n) % 1000000007 << endl;
- cout << OMI(10, 1000000007) << endl;
- cout << binomialCoeff(20, 10);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement