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!!

view plainprint?

1. const LL MOD = 1000000007LL;  
2.   
3. LL dp[10+1][1<<10];  
4. LL ptr[1<<10][1<<10];  
5.   
6. void init(int x, int y, int b) {  
7.     if ((1<<b) > x) return;  
8.   
9.     init(x, y, b+1);  
10.     if (x >> b & 1) {  
11.         init(x, y | 1<<b, b+1);  
12.         ++ptr[x][y | 1<<b] %= MOD;  
13.     }  
14.     if ((x >> b & 1) && (x >> (b+1) & 1)) {  
15.         init(x, y | 3<<b, b+2);  
16.         ++ptr[x][y | 3<<b] %= MOD;  
17.     }  
18.     if ((x >> b & 1) && (x >> (b+2) & 1)) {  
19.         init(x, y | 7<<b, b+3);  
20.         ++ptr[x][y | 7<<b] %= MOD;  
21.     }  
22. }  
23.   
24. class SmallBricks31 {  
25. public:  
26.     int countWays(int w, int h) {  
27.         memset(dp, 0, sizeof(dp));  
28.         memset(ptr, 0, sizeof(ptr));  
29.   
30.         REP(i, 1<<10) {  
31.             if (i > 0) {  
32.                 int b = 0;  
33.                 while (!(i & 1<<b))  
34.                     ++b;  
35.                 init(i, 0, b);  
36.             }  
37.         }  
38.   
39.         dp[0][(1<<w)-1] = 1;  
40.         REP(i, h) REP(j, 1<<w) {  
41.             if (!dp[i][j]) continue;  
42.   
43.             REP(k, 1<<w) {  
44.                 if (ptr[j][k]) {  
45.                     LL tmp = dp[i][j] * ptr[j][k] % MOD;  
46.                     dp[i+1][k] = (dp[i+1][k] + tmp) % MOD;  
47.                 }  
48.             }  
49.         }  
50.   
51.         LL ret = 0;  
52.         FOR (i, 1, h+1) REP(j, 1<<w) ret = (ret + dp[i][j]) % MOD;  
53.   
54.         return ++ret % MOD;  
55.     }  
56. };  

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