动态规划递推计算，记录每一种状态$(a,b,c)$的数字串总数。
其中a,b都是N位二进制数，交表示模d以及d-1余r的数是否出现过，c记录是否已经有过能整除d的子串。
从左到右依次添加数位并更新状态即可，最终结果是$3079418648040719$。
注：因用到walrus算符，以下代码为Python 3。
from collections import defaultdict
r=0
for n in range(1,20):
d=defaultdict(int)
for i in range(1,10):
d[(1 << (i%n),0,i%n==0)]+=1
for i in range(n-1):
d,d2=defaultdict(int),d
for a,b,c in d2:
for j in range(10):
a2=b2=0
c2=c
for k in range(n):
if x:=(k==0)+((a & (1 << k))!=0)+((b & (1 << k))!=0):
z=(k*10+j)%n
if z==0:
if c2+x>1:
break
c2=True
if (a2 & (1 << z)) or x>1:
b2|=1 << z
a2|=1 << z
else:
d[a2,b2,c2]+=d2[a,b,c]
print("n=",n,"completed")
r+=sum(d[(a,b,c)] for a,b,c in d if c)
print(r)
|
