usaco_nocows-求有n个节点高度是k的二叉树有多少个.cpp

来自「usaco自己做的1到5章的代码」· C++ 代码 · 共 49 行

/*ID: wangyuc2
PROG: nocows
LANG: C++*/
/*
这道题的意思就是求有N个节点高度是k的二叉树有多少个

有dp求解,一开始虽然想到了dp,但还是在看了题解后才做出来的

F[i,j]=∑F[i-1,d]*F[i-1,j-1-d]

最大高度是i,j个节点的二叉树一共有F[i,j]种组成的方法

等于最大高度是i-1,d个节点的二叉树和j-1-d个节点的二叉树的积,乘法原理.d属于1..j-2,而且j,d,j-1-d要是奇数

边界条件是F[i,1]=1;

在有就是在实现时要随时的mod9901,至于为什么则是数论的知识

*/
#include <fstream>
#include <iostream>
#include <memory>
#include <algorithm>
using namespace std;
ifstream fin("nocows.in");
ofstream fout("nocows.out");
int main()
{
      int n,k,i,j,l;
      long int f[200][100];  
      fin>>n>>k;  
      if(n % 2 == 0) 
      {
           fout<<'0'<<endl; 
           exit(0);
      }  
      memset(f,0,sizeof(f));  
      for(i=1;i<=k;i++) f[1][i]=1;  
      for(j=1;j<=k;j++) 
           for(i=1;i<=n;i=i+2)  
                 for(l=1;l<=i-2;l++)        
                 {            
                     f[i][j]=(f[i][j]+f[l][j-1]*f[i-l-1][j-1])%9901;            //f[i][j]%=9901;  
                 }  
      fout<<(f[n][k]-f[n][k-1]+9901)%9901<<endl;  
      //system("PAUSE");
      return 0;
}