令$cr(n)$,$cg(n)$,$cb(n)$,$bb(n)$分别为摆成长度为$n$的一行时以红、绿、蓝、黑色块结尾的摆法总数。
与第114题、第115题、第116题类似，有如下递推公式
\begin{align*}
bb(n)&=cr(n-1)+cg(n-1)+cb(n-1)+bb(n-1) \\
cr(n)&=cr(n-2)+cg(n-2)+cb(n-2)+bb(n-2) \\
cg(n)&=cr(n-3)+cg(n-3)+cb(n-3)+bb(n-3) \\
cb(n)&=cr(n-4)+cg(n-4)+cb(n-4)+bb(n-4) \\
\end{align*}
n从0取至5时的初值为
\begin{align*}
cr&=(0,0,1,1,2,4) \\
cg&=(0,0,0,1,1,2) \\
cb&=(0,0,0,0,1,1) \\
bb&=(0,1,1,2,4,8)
\end{align*}
递推即得结果$100808458960497$。
cr=[0,0,1,1,2,4]
cg=[0,0,0,1,1,2]
cb=[0,0,0,0,1,1]
bb=[0,1,1,2,4,8]
for i in range(6,51):
cr.append(cr[i-2]+cg[i-2]+cb[i-2]+bb[i-2])
cg.append(cr[i-3]+cg[i-3]+cb[i-3]+bb[i-3])
cb.append(cr[i-4]+cg[i-4]+cb[i-4]+bb[i-4])
bb.append(cr[i-1]+cg[i-1]+cb[i-1]+bb[i-1])
print cr[50]+cg[50]+cb[50]+bb[50]
|
