[ create a new paste ] login | about

Link: http://codepad.org/Y6lbj6eM    [ raw code | output | fork ]

C++, pasted on Sep 18:
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;

const int MaxN = 2000 +10;
const int mods = 10000+7;
int N;
long ms[MaxN],F[MaxN][MaxN],ans,ls[MaxN];

long dp(int t,int h){
    if(t>ms[h] || t<ls[h]) return 0;
    if(t==ms[h]) return 1;
    if(F[t][h]) return F[t][h];
    long tans=0;
    if(h==1){
        if(t==1) return 1;
        else return 0;
    }
    if(h==2){
        if(t==3) return 1;
        if(t==2) return 2;
        return 0;
    }
    for(int i=1;i<t;i++){
        tans=(tans+dp(i,h-1)*dp(t-1-i,h-1))%mods;
        tans=(tans+dp(i,h-1)*dp(t-1-i,h-2))%mods;
        tans=(tans+dp(i,h-2)*dp(t-1-i,h-1))%mods;
    }
    return F[t][h]=(tans)%mods;
}

int main(){
    freopen("1.in","r",stdin);
    scanf("%d",&N);
N=5;
    ms[1]=1;
    ls[1]=1;
    ms[2]=3;
    ls[2]=2;
    int u=3;
    for(;ls[u-1]<=2000;u++){
        ms[u]=(ms[u-1]+1)*2-1;
        ls[u]=ls[u-1]+ls[u-2]+1;
    }
    for(int h=1;h<u;h++) ans=(ans+dp(N,h))%mods;
    printf("%ld\n",ans);
    return 0;
}


Output:
1
6


Create a new paste based on this one


Comments: