对于任意两个数字串A和B，定义$F_{A,B}$为序列$A, B, AB, BAB, ABBAB, \ldots$，即从第三项起每一项都是前两项拼接而成。

取$F_{A,B}$中首个至少有n位的项，并记这一项的第n个数字为$D_{A,B}(n)$。

例如，取$A=1415926535$，$B=8979323846$，则$F_{A,B}$的前几项依次是： \begin{align*} &1415926535, \\ &8979323846, \\ &14159265358979323846, \\ &897932384614159265358979323846, \\ &1415926535897932384689793238461415\textcolor{red}{9}265358979323846. \end{align*} 因此$D_{A,B}(35)$是第五项的第35个数字，也就是9。

现取A为圆周率$\pi$小数点后的前100位数字： \begin{align*} &14159265358979323846264338327950288419716939937510 \\ &58209749445923078164062862089986280348253421170679 \end{align*} B为第101到第200位数字： \begin{align*} &82148086513282306647093844609550582231725359408128 \\ &48111745028410270193852110555964462294895493038196 \end{align*} 求$\sum_{n=0}^{17}10^nD_{A,B}\left(7^n(127+19n)\right)$。

本题难度:

解答

记$x_n=7^n(127+19n)$，则结果事实上就是$D_{A,B}(x_17),\ldots,D_{A,B}(x_0)$拼接成的数字串。

用一个列表记录$F_{A,B}$中每一项的长度，遍历$x_n$，只要表末的长度小于$x_n$就添加新的元素。

假设首个至少有$x_n$位的项是第$i_n$项$W_{i_n}$，则由于$W_{i_n}$是由$W_{i_n-2}$和$W_{i_n-1}$拼接而成，根据$x_n$是否大于$W_{i_n-2}$的长度可以继续递归地在$W_{i_n-2}$或$W_{i_n-1}$中搜索，直到定位到A、B之一为止。

结果是$850481152593119296$。

A="1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
B="8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"

a=[100,100]

def find(i,x):
    if i==0:
        return A[x-1]
    elif i==1:
        return B[x-1]
    else:
        return find(i-2,x) if x <= a[i-2] else find(i-1, x-a[i-2])

r=""
for n in range(18):
    x=(127+19*n)*(7**n)
    while a[-1] < x:
        a.append(a[-2]+a[-1])   
    r=find(len(a)-1,x)+r

print r