USACO Training Section 2.3 Cow Pedigrees

英文原题  中文题译

大意：给定节点数和树的高度，求完全二叉树的个数。

很多磨的一题。思路很清晰，DP也不难，关键在于边界条件处理，以及注意是完全二叉树，这样，左右子树要至少有一个节点或者为叶子节点。从而，偶数节点数的计数必然为0。

本来一个小时之前就还算顺利的做好了，但35,7的时候对，99 15的时候不对，晕了。头痛了半天，打开标程看了看，它计算lower的方式是通过full来做的。想了半天，怀疑自己的lower递归写错，于是按标程的思路重写了一遍。写完，马上骂自己是猪。想想这里的结果是摸P的（结果太大）,P=9901。也就是说，在计算中可能超出整数上限导致出错。而35 7既然对，那么错就错在模P上。这才想起来在原来的实现中每次计算都模了P但最后结果没模P，晕倒。回头一看，原程序已不见了，又重头写过，处理边界条件时已经头痛的厉害，总算搞定。唉。难道真的是老了？？？？

注：没优化了，用对称性可以使计算量减半。

/*
ID: blackco3
TASK: nocows
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std ;
#define _max_node_ 300
#define _max_high_ 100
const int P = 9901 ;
int _node, _high ;
int lower[_max_node_+1][_max_high_], full[_max_node_+1][_max_high_+1] ;

int main() {
    freopen("nocows.out", "w", stdout);
    freopen("nocows.in", "r", stdin);
	cin >> _node >> _high;
	memset( lower, 0, sizeof(lower) );
	memset( full, 0, sizeof(full) );

	for( int i=2; i<=_high; i++ )
		lower[1][i]=1;
	for( int h=2; h<_high; h++ )
		for( int n=3; n<=_node; n+=2 ){
			for( int ln=1; ln<=n-1; ln+=2 )
				lower[n][h] += ( lower[ln][h-1]*lower[n-ln-1][h-1] ) % P ;
			lower[n][h] %= P ;
		}

	full[1][1]=1 ;
	for( int h=2; h<=_high; h++ )
		for( int n=3; n<=_node; n+=2 ){
			for( int ln=1; ln<=n-1; ln+=2 ){
				full[n][h] += ( full[ln][h-1]  * full[n-ln-1][h-1]  ) % P;
				full[n][h] += ( full[ln][h-1]  * lower[n-ln-1][h-1] ) % P;
				full[n][h] += ( lower[ln][h-1] * full[n-ln-1][h-1]  ) % P;
			}
			full[n][h] %= P ;
		}
	cout <<  full[_node][_high] << endl ;
	return 0;
}