SPOJ, TRECOUNT, DP

SPOJ-TRECOUNT.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;
const ull MOD = 1000000000ULL;
const int MH=15;
ull dp[MH+2][4096];
unsigned mn[MH+2], mx[MH+2];
void pre1(){
  mn[0]=1; mx[0]=1;
	mn[1]=2; mx[1]=3;
	for(int i=2;i<=MH;i++){
		mn[i] = mn[i-1] + mn[i-2]+1;
		mx[i] = (1<< (i+1)) - 1;
	}
}

void pre2(){
	dp[0][1]=1;
	dp[1][2]=2;
	dp[1][3]=1;
	for(int h=2;h<=MH;h++){
		for(int n=mn[h];n<=mx[h] && n<1500;n++){
				for(int ln=mn[h-2];ln<=mx[h-1] && ln<=n;ln++){
					int rn = n - ln - 1;
					if(rn < 0) continue;
					dp[h][n] += dp[h-1][ln] * dp[h-1][rn];
					dp[h][n] += dp[h-1][ln] * dp[h-2][rn];
					dp[h][n] += dp[h-2][ln] * dp[h-1][rn];
					if(dp[h][n]>=MOD)
						dp[h][n] %= MOD;
				}				
			}
		}
}

int main()
{
	pre1();
	pre2();
	int T=1,N;
	ull R;
	//cin >> T;
	while(T){
		cin >> N;
		if(cin.eof())
			{return 0;}
		R=0;
		for(int i=0;i<=MH;i++){
			R = R + dp[i][N];
			if(R>=MOD)
				R%= MOD;
			}
		printf("%09llu\n", R);
	}
	return 0;
}