codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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; }
Private
[
?
]
Run code
Submit