AOJ - POLY

AOJ - POLY

세로를 보지말고 가로로 정사각형들을 쌓는다고 하자.

$dp[ \text{remain} ][ \text{last\_len} ]=$ 현재 남은 블럭이 remain 개이고 바로 위 블럭이 쌓아진 칸의 길이가 last_len 일 때, 계속 쌓았을 때 정답의 수

문제에서 설명하는 도형을 만들기 위해 정사각형은 항상 1자로 붙여서 가로로 쌓아야 한다는 것을 알 수 있고, 다음에 쌓을 개수가 $K$ 라면 $K+\text{last\_len}-1$ 개의 경우의 수를 쌓을 수 있다.

따라서

$dp[\text{remain}][\text{last\_len}]= \begin{cases} \displaystyle\sum_{k=1}^{\text{remain}}\left( (K+\text{last\_len}-1) \cdot dp[ \text{remain}-K][K] \right)\\ 1~(\text{remain}=0) \end{cases}$

const ll mod = 1e7;  
inline ll md(ll x) { return md(mod, x); }  
int dp[222][222];  
  
int fn(int remain, int last_len) {  
   if (remain == 0) return 1;  
   int &ret = dp[remain][last_len];  
   if (~ret) return ret;  
   ret = 0;  
   for (int nxt_len = 1; nxt_len <= remain; nxt_len++) {  
      ret = md(ret + fn(remain - nxt_len, nxt_len) * (nxt_len + last_len - 1));  
   }  
   return ret;  
}  
  
void solve() {  
   int n;  
   cin >> n;  
   memset(dp, -1, sizeof dp);  
   int ans = 0;  
   for (int len = 1; len <= n; len++) {  
      ans = md(ans + fn(n - len, len));  
   }  
   cout << ans << endl;  
}