10422번: 괄호

https://www.acmicpc.net/problem/10422


$O(l^2+t)$

카탈란 수열이다.

#include<cstdio>
int t, l, c[2501] = { 1 };
int main() {
    for (int i = 1; i < 2501; i++)
        for (int j = 0; j < i; j++) c[i] = (c[i] + 1LL * c[j] * c[i - 1 - j]) % 1000000007;
    for (scanf("%d", &t); t--;) scanf("%d", &l), printf("%d\n", l & 1 ? 0 : c[l / 2]);
    return 0;
}