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;
    }
};