1670번: 정상 회담 2

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


$O(n^2)$

카탈란 수열이다.

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