HDU 1400 - Mondriaan's Dream
Problem : Given a n*m grid. Show the number of ways to put the 1x2 and 2x1 rectangle to full it.
Solution : Let S(x) to be the status s.t. the i-th bit of x is 1 if and only if there is a 2x1 rectangle stand on the i-th grid of the row. valid[x] is 1 if and only if the row in S(x) can be fulled by 1x2 rectangles. t[x][y] is 1 if and only if (x bit-and y = 0) and valid[(x bit-or y)]=1. Denote f[i][x] to be the number of ways s.t. the rows before i are all fulled and rows below i are all not occupied, the status of i-th row is S(x). Then f[i][x]=sum{f[i-1][y] | t[y][x]=1}, f[1][x]=(1)1 if x=0. (2)0 otherwise.