考虑排成一行的无限多个盒子，其中一些盒子里放了球。

一种放置方法是在两个盒子中放球，接着跳过两个箱子，然后再在两个盒子中放球，再跳过一个空箱子，接下来又再在两个盒子中放球，这样的放置方法可以表示为序列(2, 2, 2, 1, 2)，即序列中的数依次表示放球的盒子和不放球的盒子的数量。

若每轮都依次将最左侧的尚未移动过的球移动到其右边离它最近的空格，每个球移动恰好一次，则第一轮后，序列(2, 2, 2, 1, 2)将转化为(2, 2, 1, 2, 3)，且可以看出，经过充分多轮后，该系统将演化到一个不变状态，如下图：

本例的最终状态中有球的盒子的数量依次是[1,2,3]。若按以下方式定义序列{ti}： \begin{align*} s_0&=290797 \\ s_{k+1}&=s_k^2 \bmod 50515093 \\ t_k&=(s_k \bmod 64)+1 \end{align*} 则从初始状态$(t_0, t_1, \ldots, t_{10})$开始时，最终状态中有球的盒子的数量将依次是[1, 3, 10, 24, 51, 75]。

求从初始状态$(t_0, t_1, \ldots, t_{10^7})$开始时，最终状态中有球的盒子的数量。答案需要以各元素的平方和的形式给出，例如，若最终状态是[1, 2, 3]，则你的答案应当是14，因为$14=1^2+2^2+3^2$。

本题难度:

解答

本题似乎是与可积系统有关，但有一个简单规律即若序列末尾是(a,b,c)且b小于a和c，就可以将这三项替换为$a+c-b$并把b的平方计入结果。

最后再在剩余的序列中计入有球的项的平方和即得最终结果$31591886008$。

N=10**7
res=0
a=[]
s=290797
while N>=0:
    a.append((s%64)+1)
    s=(s*s)%50515093
    N-=1
    while len(a)>=3 and a[-2] <= a[-3] and a[-2] <= a[-1]:
        res+=a[-2]*a[-2]
        a.append(a.pop()-a.pop()+a.pop())

print res+sum(a[i]*a[i] for i in range(len(a)-1,-1,-2))