SRM 523 Div1 Med BricksN
dp[W][H]:=上からH段目まで横幅Wのブロックの置き方
#include <cstring> using namespace std; typedef long long ll; #define MOD 1000000007 class BricksN { public: ll num[55]; ll dp[55][55]; ll rec(int W,int H) { if(H==0||W<=0)return 1ll; if(dp[W][H]!=-1)return dp[W][H]; ll res=0ll; for(int i=0;i<=W;i++) { res+=((num[i]*rec(i,H-1))%MOD)*rec(W-1-i,H)%MOD; res%=MOD; } return dp[W][H]=res; } int countStructures(int w, int h, int k) { memset(num,0,sizeof(num)); memset(dp,-1,sizeof(dp)); num[0]=1; for(int i=1;i<=w;i++) { for(int j=1;j<=k;j++) { if(i-j>=0) { num[i]+=num[i-j]; num[i]%=MOD; } } } return rec(w,h); } };