本题是典型的动态规划问题，先考虑一行的所有可能砌法。
设$1\times 2$和$1\times 3$的砖块各有x,y块，则$2x+3y=32$，x可以分别取1,4,7,10,13,16，y的对应值为10,8,6,4,2,0。
对每组x,y，从$x+y$个位置中选出x个放置$1\times 2$的砖块，取遍所有的可能的组合即都一行的所有可能砌法。
每行的32格中有31条内部边界，因此用一个31位的二进制数来表示每种砌法中这31条内部边界的状态，0表示不是接缝，1表示是接缝。
若a,b分别是上下两行的砌法所对应的二进制数，那么题目要求$a\& b=0$，其中$\&$表示按二进制位作与运算。
因此先生成所有砌法对应的二进制数列表（共有三千多个可能的状态），再双循环找出对其中每个数a，满足$a\& b=0$的b，记录在字典中。
用函数$c(i,j)$表示在第i行使用j砌法的总方法数，则
$$c(i,j)=\sum_{k\& j=0}c(i-1,k),$$
最后递推汇总即得结果$806844323190414$。
import itertools
status=[int("".join("01" if i in c else "001" for i in range(x+y))[:-1],2) for x,y in [(1,10),(4,8),(7,6),(10,4),(13,2),(16,0)] for c in itertools.combinations(range(x+y),x)]
n=len(status)
d={i:[j for j in range(n) if status[i]&status[j]==0] for i in range(n)}
c=[[1]*n for i in range(10)]
for i in range(1,10):
for j in range(n):
c[i][j]=sum(c[i-1][k] for k in d[j])
print sum(c[-1])
|
