## 2011年11月22日火曜日

### SRM 523 DIV2 1000 smallbricks31

On top of the basement of size 1*1*w, we like to construct a building object using three types of bricks, whose sizes are 1*1*1, 1*1*2, 1*1*3, respectively. The height of the building is at most h. How many different type of buildings could you construct under some constraints? -- A concise summery is like that.

At first glance, I was like, "Umm, this is a simple bit DP problem." But it took me longer to implement the idea than I thought. Guess I have to solve this level of problem within 30 minutes to be a yellow coder. Just need more practices!!

`const LL MOD = 1000000007LL;LL dp[10+1][1<<10];LL ptr[1<<10][1<<10];void init(int x, int y, int b) {    if ((1<<b) > x) return;    init(x, y, b+1);    if (x >> b & 1) {        init(x, y | 1<<b, b+1);        ++ptr[x][y | 1<<b] %= MOD;    }    if ((x >> b & 1) && (x >> (b+1) & 1)) {        init(x, y | 3<<b, b+2);        ++ptr[x][y | 3<<b] %= MOD;    }    if ((x >> b & 1) && (x >> (b+2) & 1)) {        init(x, y | 7<<b, b+3);        ++ptr[x][y | 7<<b] %= MOD;    }}class SmallBricks31 {public:    int countWays(int w, int h) {        memset(dp, 0, sizeof(dp));        memset(ptr, 0, sizeof(ptr));        REP(i, 1<<10) {            if (i > 0) {                int b = 0;                while (!(i & 1<<b))                    ++b;                init(i, 0, b);            }        }        dp[0][(1<<w)-1] = 1;        REP(i, h) REP(j, 1<<w) {            if (!dp[i][j]) continue;            REP(k, 1<<w) {                if (ptr[j][k]) {                    LL tmp = dp[i][j] * ptr[j][k] % MOD;                    dp[i+1][k] = (dp[i+1][k] + tmp) % MOD;                }            }        }        LL ret = 0;        FOR (i, 1, h+1) REP(j, 1<<w) ret = (ret + dp[i][j]) % MOD;        return ++ret % MOD;    }};`