Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- const long long int pr = pow(10, 9) + 7;
- unsigned long int catalanDP(unsigned int n)
- {
- unsigned long int* catalan = new unsigned long int[n + 1];
- catalan[0] = catalan[1] = 1;
- for (int i = 2; i <= n; i++)
- {
- catalan[i] = 0;
- for (int j = 0; j < i; j++)
- {
- catalan[i] += ((catalan[j] % pr) * (catalan[i - j - 1] % pr)) % pr;
- catalan[i] %= pr;
- }
- }
- unsigned long int res = catalan[n] % pr;
- delete[] catalan;
- return res;
- }
- int main()
- {
- long int n;
- cin >> n;
- n /= 2;
- cout << catalanDP(n) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement