每個樹的狀態都由其左右子樹狀態決定,根據乘法原理,其狀態數等於左右子樹狀態數乘積 題目限制了數樹的深度

dp[n,k]=∑(dp[n,k-1]*dp[n-1-i,k-1])(i∈1..i-2) 邊界條件：dp[1,i]=1

結果就是 dp[N][K]-dp[N][K-1]

注意考慮與9901求餘

/*
ID: cmykrgb1
PROG: nocows
LANG: C++
*/
#include <stdio.h>
FILE *fi,*fo;
long int N,K;
long int dp[201][100];

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


int main(void)
{
    int i;
    fi=fopen("nocows.in","r");
    fo=fopen("nocows.out","w");
    fscanf(fi,"%d %d",&N,&K);
    fclose(fi);
    for (i=1;i<=K;i++)
        dp[1][i]=1;
    dynamicp();
    fprintf(fo,"%ldn",((dp[N][K]+9901-dp[N][K-1])%9901));
    fclose(fo);
    return 0;
}