USACO 2.3 Cow Pedigrees

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <unordered_set>

using namespace std;

int N, K;
const int MOD = 9901;

int main() {
    ifstream fin("nocows.in");
    ofstream fout("nocows.out");
    fin >> N >> K;
    vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= K; ++i) {
        dp[i][1] = 1;
    }

    for (int i = 1; i <= K; ++i) {
        for (int j = 1; j <= N; j+= 2) {
            for (int k = 1; k <= j - 2; ++k) {
                dp[i][j] = (dp[i][j] +
                            dp[i - 1][k] * dp[i - 1][j - k - 1]) % MOD;
            }
        }
    }

    int result = (dp[K][N] - dp[K - 1][N] + MOD) % MOD;
    fout << result << endl;
}