容易想到需要在数位上作动态，实现中将其转换为字典树上的动态规划。
以下代码改编自官方论坛，非常简洁快速，应该很难有更好的实现。
本题的最终结果是$1295552661530920149$。
注：因用到一些新的语法特性（例如*运算符），以下代码为Python 3。
import collections,math
N=10**18
Node=collections.namedtuple("Node", "size count children")
EMPTY=Node(0,0,None)
bases=[11**n for n in range(1,18)]
paths=[tuple(int(c) for c in str(b)) for b in bases]
def intervals(size):
digits=math.ceil(math.log10(size))
for p in paths:
if len(p)>digits:
break
yield (p,10**(digits-len(p)))
def expand(tree):
return Node(tree.size*10, tree.count*10, (tree,)*10)
def exclude(tree, path, size):
if tree.count==0:
return None
if tree.size==size:
return EMPTY
pos,*rest=path
oldChild=tree.children[pos]
newChild=exclude(oldChild,rest,size)
return Node(tree.size, tree.count-oldChild.count+newChild.count, tree.children[:pos]+(newChild,)+tree.children[pos+1:]) if newChild else None
def E(tree, n):
if tree.size==1:
return 1
for i,c in enumerate(tree.children):
if n<=c.count:
return i*c.size+E(c,n)
else:
n-=c.count
root=Node(1,1,())
while root.count<=N:
root=expand(root)
for path,size in intervals(root.size):
root=exclude(root,path,size) or root
print(E(root,N))
|
