最后一问

给定字符串： $$thereisasyetinsufficientdataforameaningfulanswer$$ 从其中选取不超过15个字母，并按任意顺序排列后形成一个新的字符串。

将所有可能获得的字符串按字典序排列，并从1开始编号如下： \begin{align*} 1 : &a \\ 2 : &aa \\ 3 : &aaa \\ 4 : &aaaa \\ 5 : &aaaaa \\ 6 : &aaaaaa \\ 7 : &aaaaaac \\ 8 : &aaaaaacd \\ 9 : &aaaaaacde \\ 10 : &aaaaaacdee \\ 11 : &aaaaaacdeee \\ 12 : &aaaaaacdeeee \\ 13 : &aaaaaacdeeeee \\ 14 : &aaaaaacdeeeeee \\ 15 : &aaaaaacdeeeeeef \\ 16 : &aaaaaacdeeeeeeg \\ 17 : &aaaaaacdeeeeeeh \\ \vdots& \\ 28 : &aaaaaacdeeeeeey \\ 29 : &aaaaaacdeeeeef \\ 30 : &aaaaaacdeeeeefe \\ \vdots& \\ 115246685191495242: &euleoywuttttsss \\ 115246685191495243: &euler \\ 115246685191495244: &eulera \\ \vdots& \\ 525069350231428029: &ywuuttttssssrrr \end{align*} 令$P(x)$为字符串$x$在该表中的位置，再令$W(n)$为表中的第$n$个字符串，则有$P(W(n))=n$以及$W(P(x))=x$。

求$W(P(``legionary'')+P(``calorimeters'')-P(``annihilate'')+P(``orchestrated'')-P(``fluttering''))$。

注：《最后一问》是美国科幻作家艾萨克·阿西莫夫1956年出版的一部科幻小说，本题中的字符串是其中的一句台词也是全书的线索。

本题难度:

解答

只需构造出W或P中的一个即可用二分查找构造另一个。

P的构造相对容易一些，给定要检验的字符串x，遍历其中的字符，根据当前字符计算在当前位置处小于给字符的字符串总数（此步可记忆化存储结果）即可。

最终结果是turnthestarson

注：因使用cache装饰器作记忆化搜索，以下代码为Python 3。只需构造出W或P中的一个即可用二分查找构造另一个。

P的构造相对容易一些，给定要检验的字符串x，遍历其中的字符，根据当前字符计算在当前位置处小于给字符的字符串总数（此步可记忆化存储结果）即可。

最终结果是turnthestarson

注：因使用cache装饰器作记忆化搜索，以下代码为Python 3。

from collections import Counter
from functools import *

phrase="thereisasyetinsufficientdataforameaningfulanswer"
N=15

counts=sorted(Counter(phrase).most_common())
letters="".join(x for x,_ in counts)
amounts=[y for _, y in counts]

f=lambda a,i:tuple(sorted(v-1 if u==i else v for u,v in enumerate(a) if (u==i and v>1) or (u!=i and v>0)))

@cache
def arrange(a,n):
    return 1 if n==0 else 1+sum(arrange(f(a,i), n-1) for i,c in enumerate(a))
    
def P(x):
    s=""
    t=list(amounts)
    pos=1
    for c in x:
        k=letters.find(c)
        pos+=1+sum(arrange(f(t,i),N-len(s)-1) for i in range(k) if t[i]!=0)
        s+=c
        t[k]-=1
    return pos-1
    
def W(m):
    s=""
    t=list(amounts)
    while P(s)!=m:
        i=len(t)-1
        while i>=0 and (t[i]==0 or P(s+letters[i])>m):
            i-=1
        s+=letters[i]
        t[i]-=1
    return s
    
print(W(P("legionary")+P("calorimeters")-P("annihilate")+P("orchestrated")-P("fluttering")))