246
Cerința
Să se determine numărul de șiruri de lungime 2 * n
care conțin paranteze închise corect.
Date de intrare
Programul citește de la tastatură numărul n
.
Date de ieșire
Programul va afișa pe ecran restul împărțirii numărului de șiruri de lungime 2 * n
, care sunt parantezate corect, la 666013
.
Restricții și precizări
1 ≤ n ≤ 1000
Exemplu
Intrare
3
Ieșire
5
Explicație
((()))
, ()(())
, ()()()
, (())()
, (()())
.
#include <bits/stdc++.h> using namespace std; #define MOD 666013 unsigned long long a[1001] , n; int main() { cin >> n; a[0] = 1; a[1] = 1; for(int i = 2; i <= n ; ++i) for(int j = 0; j < i ; ++j) a[i] = (a[i] + (a[j] * a[i - j - 1])) % MOD; cout << a[n] % MOD; return 0; }
Comentarii