用memoization dp解。
用dp[n][k]來(lái)記錄結(jié)點(diǎn)數(shù)為n，高度<=k的樹(shù)的形態(tài)的個(gè)數(shù)。
由于樹(shù)的結(jié)點(diǎn)的度數(shù)只可能為0或2，這個(gè)樹(shù)的結(jié)點(diǎn)總數(shù)必然是個(gè)奇數(shù)。（推導(dǎo)很簡(jiǎn)單，一般數(shù)據(jù)結(jié)構(gòu)書(shū)都會(huì)有，略）
樹(shù)的高度最高為(n-1)/2。
dp[n][k]= dp[1][k-1]*dp[n-2][k-1]+dp[2][k-1]*dp[n-3][k-1]+...+dp[n-2][k-1]*dp[1][k-1];
利用對(duì)稱性質(zhì)，可以節(jié)省一半計(jì)算。
dp[1][1]是遞歸的出口。
有了dp[n][k]了，求高度恰好等于k的樹(shù)的形態(tài)的個(gè)數(shù)就很顯然dp[n][k]-dp[n][k-1]可得。
由于要模上9901,注意可能是負(fù)值，所以要先加上9901再求模。
代碼如下：
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("nocows.in");
ofstream?fout("nocows.out");
int?dp[200][100];
int?n,k;
int?ped_num(int?node,int?height);
void?solve()
{
????memset(dp,-1,sizeof(dp));
????dp[1][1]?=?1;
????in>>n>>k;
????out<<(ped_num(n,k)-ped_num(n,k-1)+9901)%9901<<endl;
}
int?ped_num(int?node,int?height)
{
????if(node%2!=1)?return?0;
????if(height>(node+1)/2)
????????height?=?(node+1)/2;
????if(dp[node][height]!=-1)
????????return?dp[node][height];
????int?res?=?0;
????for(int?i=1;i<(node-1)/2;i+=2){
????????res+=ped_num(i,height-1)*ped_num(node-1-i,height-1);
????????res%=9901;
????}
????res*=2;
????int?tmp?=?ped_num((node-1)/2,height-1);
????res+=tmp*tmp;
????res%=9901;
????dp[node][height]?=?res;
????return?res;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}