令$a_n$为长度为n的摆法中以红色块结尾的摆法总数，$b_n$为长度为n的摆法中以黑色块结尾的摆法总数，考虑在最后添加一块的情形:
添加黑色块总是组合规则的，因此
$$b_{n+1}=a_{n}+b_n.$$
由于红色块的最小长度是3，因此它只能添加在红色块后（否则最后两格为黑1+红1不合规则），此外，长度为n+1且以红色块结尾的摆法还可以通过取长度为n-2且以黑色块结尾的摆法，并在其后连续添加3个红色块得到，因此
$$a_{n+1}=a_{n}+b_{n-2}.$$
易知初值为
$$a_1=a_2=0, a_3=1,\quad b_1=b_2=b_3=1.$$
递推即得$a_{50}+b_{50}=16475640049$。
a=[0,0,0,1]
b=[0,1,1,1]
for i in range(4,51):
b.append(a[i-1]+b[i-1])
a.append(a[i-1]+b[i-3])
print a[50]+b[50]
|
