Skip to content

Instantly share code, notes, and snippets.

@osjayaprakash
Created January 16, 2013 06:30
Show Gist options
  • Save osjayaprakash/4545093 to your computer and use it in GitHub Desktop.
Save osjayaprakash/4545093 to your computer and use it in GitHub Desktop.
SPOJ, TRECOUNT, DP
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment