洛谷 1472 奶牛家谱 Cow Pedigrees
【题解】
DP题，我们用f[i][j]表示有n个节点、高度小于等于j的二叉树的个数。f[i][j]=sigma(f[t][j-1]*f[i-t-1][j-1]) t是1~i-1范围内的奇数。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 300 7 using namespace std; 8 LL n,k,f[N][N],Mod; 9 inline int read(){ 10 int k=0,f=1; char c=getchar(); 11 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 12 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 13 return k*f; 14 } 15 int main(){ 16 n=read(); k=read(); Mod=9901; 17 for(rg int i=1;i<=k;i++) f[1][i]=1; 18 for(rg int j=1;j<=k;j++) 19 for(rg int i=1;i<=n;i++) 20 for(rg int t=1;t<i;t+=2) 21 f[i][j]+=f[t][j-1]*f[i-t-1][j-1]%Mod,f[i][j]%=Mod; 22 printf("%lld ",(f[n][k]-f[n][k-1]+Mod)%Mod); 23 return 0; 24 }