This post is written in Chinese. Please consider using Google Translate

每个树的状态都由其左右子树状态决定,根据乘法原理,其状态数等于左右子树状态数乘积 题目限制了数树的深度

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;
}