每行有两种三角形，称$\Delta$为正三角形，$\nabla$为逆三角形，并用$0,1,2$分别表示红绿蓝三种颜色。
显然只有正三角形的染色会影响下一行，因此每行用一个不超过8位的三进制数来表示该行中正三角形的颜色，并用$f(i,j)$表示共i行的三角阵内最后一行正三角的染色方案为j时的有效染色方案总数，其中$0\le j < 3^i$。
第i行的第j个正三角形与第i+1行的第j个和第j+1个正三角形共同围成一个两行的三角阵，其正中是一个逆三角形，其颜色可以有2种（周围3个正三角形同色），1种（周围3个正三角形中有两种不同颜色）和0种（周围3个正三角形都异色，是无效方案)。
预处理生成$3^8=6561$以内所有数的三进制表达，递推计算$f(i,j)$，初值为$f(1,0)=f(1,1)=f(1,2)=1$，最后汇总得
$$\sum_jf(8,j)=10834893628237824.$$
注：以下为Python 3代码，因math.prod系Python 3中新增的函数。
import math
b=[]
for s in range(3**8):
r=""
for i in [2187, 729, 243, 81, 27, 9, 3, 1]:
r+=str(s//i)
s%=i
b.append(r)
f=[[0 for j in range(3**i)] for i in range(9)]
f[1][0]=f[1][1]=f[1][2]=1
for i in range(2,9):
for j in range(3**i):
x=b[j][8-i:]
f[i][j]=sum(t*math.prod(3-len(set([x[u],x[u+1],v])) for u,v in enumerate(b[k][9-i:])) for k,t in enumerate(f[i-1]) if t>0)
print(i,"done")
print(sum(f[8]))
|
