Advertisement
AmidamaruZXC

Untitled

Dec 8th, 2020
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.60 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const long long int pr = pow(10, 9) + 7;
  6.  
  7. unsigned long int catalanDP(unsigned int n)
  8. {
  9.     unsigned long int* catalan = new unsigned long int[n + 1];
  10.  
  11.  
  12.     catalan[0] = catalan[1] = 1;
  13.  
  14.  
  15.     for (int i = 2; i <= n; i++)
  16.     {
  17.         catalan[i] = 0;
  18.         for (int j = 0; j < i; j++)
  19.         {
  20.             catalan[i] += ((catalan[j] % pr) * (catalan[i - j - 1] % pr)) % pr;
  21.             catalan[i] %= pr;
  22.         }
  23.     }
  24.     unsigned long int res = catalan[n] % pr;
  25.     delete[] catalan;
  26.  
  27.     return res;
  28. }
  29.  
  30. int main()
  31. {
  32.     long int n;
  33.     cin >> n;
  34.     n /= 2;
  35.     cout << catalanDP(n) << endl;
  36.     return 0;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement