Advertisement
OMEGAHEAD_MonkoX

Untitled

Feb 20th, 2020
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.78 KB | None | 0 0
  1. #include <map>
  2. #include <stack>
  3. #include <set>
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. const int M = 1000000007;
  10.  
  11. int newCat(vector<long long>C, int n)
  12. {
  13. int target = 0;
  14. for (int i = 0; i < n; i++)
  15. {
  16. target = (target+C[i] * C[n - i - 1])%M;
  17. }
  18. return target;
  19. }
  20.  
  21. int newD(vector<long long>D, vector<long long>C, int n)
  22. {
  23. int target = 0;
  24. for (int i = 0; i < n; i++)
  25. {
  26. target = (target+C[i] * D[n - i - 1] + D[i] * D[n - 1 - i])%M;
  27. }
  28. return target;
  29. }
  30.  
  31. int main()
  32. {
  33. int n;
  34. cin >> n;
  35. vector<long long>D(n + 1);
  36. vector<long long>C(n + 1);
  37. D[0] = 1;
  38. C[0] = 1;
  39. for (int i = 1; i < n + 1; i++)
  40. {
  41. C[i] = newCat(C, i);
  42. D[i] = newD(D, C, i);
  43. }
  44.  
  45. cout << D[D.size() - 1];
  46.  
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement