Advertisement
Alexvans

Untitled

Jun 14th, 2017
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 KB | None | 0 0
  1. #include <iostream>
  2. #define ull unsigned long long
  3. using namespace std;
  4.  
  5. ull OMI(ull a, ull b, ull s0 = 1, ull s1 = 0) {
  6.     return b==0? s0: OMI(b, a%b, s1, s0 - s1*(a/b));
  7. }
  8.  
  9. ull binomialCoeff(ull n, ull k) {
  10.     ull res = 1;
  11.     if (k > n - k)
  12.         k = n - k;
  13.     for (ull i = 0; i < k; ++i) {
  14.         res *= (n - i);
  15.         res /= (i + 1);
  16.         //ull temp = OMI(i + 1, 1000000007);
  17.         //res *= (temp < 0) ? temp + 1000000007 : temp;
  18.     }
  19.     return res;
  20. }
  21.  
  22. ull catalan(ull n) {
  23.     ull c = binomialCoeff(2*n, n);
  24.     ull temp = OMI(n + 1, 1000000007);
  25.     //res *= (temp < 0) ? temp + 1000000007 : temp;
  26.     //return c/(n+1);
  27.     return c * ((temp < 0) ? temp + 1000000007 : temp);
  28. }
  29.  
  30. int main() {
  31.     ull n;
  32.     cin >> n;
  33.     if(n == 1) {
  34.         cout << 1;
  35.         return 0;
  36.     }
  37.     cout << catalan(n) % 1000000007 << endl;
  38.     cout << OMI(10, 1000000007) << endl;
  39.     cout << binomialCoeff(20, 10);
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement