令$b_n$为长度为n的摆法中以黑色块结尾的摆法总数，$c_n$为长度为n的摆法中以彩色色块结尾的摆法总数，并考虑在最后添加一块的情形。
用与第114题和第115题中完全相同的方法可得：若彩色块的长度为k，则有
$$b_{n}=c_{n-1}+b_{n-1}, \quad c_n=c_{n-k}+b_{n-k}+1,$$
因为显然添加黑色块总是可行的，而由于彩色块的长度必须为k，因此只可能是将一个长度为k的彩色块直接添加在长度为n-k的符合要求的摆法之后，或将其添加在前n-k块均为黑色块的摆法之后。
相应的初值为
$$c_k=c_{k+1}=b_{k+1}=1, \quad b_k=0.$$
递推即得结果$20492570929$。
cr=[0,0,1,1]
br=[0,0,0,1]
for i in range(4,51):
cr.append(cr[i-2]+br[i-2]+1)
br.append(cr[i-1]+br[i-1])
cg=[0,0,0,1,1]
bg=[0,0,0,0,1]
for i in range(5,51):
cg.append(cg[i-3]+bg[i-3]+1)
bg.append(cg[i-1]+bg[i-1])
cb=[0,0,0,0,1,1]
bb=[0,0,0,0,0,1]
for i in range(6,51):
cb.append(cb[i-4]+bb[i-4]+1)
bb.append(cb[i-1]+bb[i-1])
print cr[50]+cg[50]+cb[50]+br[50]+bg[50]+bb[50]
|
