本题的基本思想是以交点圆弧的连接方式作为状态，逐行扫描交点作动态规划。
四个角落处圆弧只有一种连接方式，四条边界上（除角落外）的每个交点处共有两种连接方式（上下开口和左右开口），内部的每个交点处有14种连接方式（可参考以下37组图形各自中心结点中非重复的形态）。
这些连接方式都可写成连接相邻两节点或连接两圆弧这两种基本连接的组合，并用括号字符串编码表示。
求出这些状态间的转移过程并递推求和即可，最终结果是$6567944538$。
一一枚举状态的编码和转移比较繁琐，以下代码摘改自官网论坛，似乎用到了纽结理论中的Jones多项式，不过这已经超出了本人知识范围。
注：因需使用函数缓存作记忆化搜索，以下代码为Python 3。
from functools import *
rows=10
cols=6
def tally(old,new,p,op):
for (s,n) in old.items():
k=op(s,p)
if k in new:
new[k]=(new[k]+n)%(10**10)
elif n and k:
new[k]=n
cup=lambda s,p:s[:p]+'()'+s[p:]
identity=lambda s,p:s
@cache
def cap(s,p):
t=s[p:p+2]
if t=='()': out=None
elif t==')(':out=s[:p]+s[p+2:]
elif t == '))':
c,n=0,p
while c>-1 and n>0:
n-=1
c+=-1 if s[n] == '(' else 1
out = s[:n] + ')' + s[n+1:p] + s[p+2:]
elif t == '((':
c,n=0,p+1
while c>-1 and n < len(s)-1:
n+=1
c+=1 if s[n] == '(' else -1
out = s[:p] + s[p+2:n] + '(' + s[n+1:]
return out
counts={'()'*cols:1}
for p in range(1,2*cols-2,2):
new = {}
temp = {}
tally(counts,temp,p,cap)
tally(temp,new,p,cup)
tally(counts,new,p,identity)
counts=new
for r in range(rows-1):
new = {}
# Add crossing on the left side
tally(counts,new,0,cup)
tally(counts,new,1,cup)
counts=new
# Add each vertex of degree 8 in this row
for c in range(cols-1):
new={}
tally(counts,new,0,identity)
temp={}
tally(counts,temp,2*c+1,cap)
tally(counts,temp,2*c+2,cap)
tally(counts,temp,2*c+3,cap)
tally(temp,new,2*c+1,cup)
tally(temp,new,2*c+2,cup)
tally(temp,new,2*c+3,cup)
temp1,temp2,temp3={},{},{}
tally(counts,temp1,2*c+1,cap)
tally(counts,temp1,2*c+2,cap)
tally(temp1,temp2,2*c+1,cap)
tally(temp2,temp3,2*c+1,cup)
tally(temp3,new,2*c+1,cup)
tally(temp3,new,2*c+2,cup)
counts=new
new={}
tally(counts,new,2*cols-1,cap)
tally(counts,new,2*cols,cap)
counts=new
for c in range(cols-1):
new={}
tally(counts,new,0,cap)
tally(counts,new,1,cap)
counts=new
print(counts['()']%(10**10))
|
