1836번: 트리의 가짓수 세기

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

$O(nk)$

dp[i][j]: 높이가 i이면서 노드 수가 j인 트리의 개수
$dp[i][j] = \sum_{k=0}^{j-1}(2*\sum_{l=1}^{i-2}dp[l][k] + dp[i-1][k])*dp[i-1][j-1-k]$
$\sum_{l=1}^{i-2}dp[l][k]$ 계산은 누적합을 이용해 빠르게 구할 수 있다.

#include<cstdio>
#define mod 9901
int dp[100][200], s[200], n, m;
int main() {
    scanf("%d%d", &n, &m);
    dp[1][1] = 1;
    for (int i = 2; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            s[j] = (s[j] + dp[i - 2][j]) % mod;
            for (int k = 0; k < j; k++)
                dp[i][j] = (dp[i][j] + (2 * s[k] + dp[i - 1][k])*dp[i - 1][j - 1 - k]) % mod;
        }
    }
    printf("%d", dp[m][n]);
    return 0;
}