数列游戏

把N个数成一行，记作序列S。

两名玩家轮流进行游戏，每名玩家需要在自己的回合选择并擦去剩余数列的第一个或最后一个数。

玩家的得分是他擦去的所有的数之和，每位玩家的目标都是使自己的得分最大。

例如$N=4$，$S=1, 2, 10, 3$时，每位玩家按最大化自己得分的策略（最优策略）时的游戏过程如下：

（1）玩家1：擦去第一个数1

（2）玩家2：擦去剩余数列的最后一个数3

（3）玩家1：擦去剩余数列的最后一个数10

（4）玩家2：擦去最后剩下的数2

最后玩家1的得分是$1+10=11$。

设S由如下规则生成，并记S有N项时双方都以最优策略游戏时玩家1的最终得分为$F(N)$。

$$s_1=0, \quad s_{i+1}=(s_i^2+45) \bmod 10^9+7$$

S的前几项分别是$0, 45, 2070, 4284945, 753524550, 478107844, 894218625, \ldots$

可以验证$F(2)=45, F(4)=4284990, F(100)=26365463243, F(10^4)=2495838522951$。

求$F(10^8)$。

本题难度:

解答

本题中N为偶数时先手是不败的，因为先手总是可以取到奇数项之和或偶数项之和这两者之一，不过此种取法得分不一定最高。

注意到若$S$中连续三项$S_{k-1}, S_k, S_{k+1}$满足$S_k>\max(S_{k-1}, S_{k+1})$，则将此三项替换为$S_{k-1}+S_{k+1}-S_k$不会改变最后的分差，因此不断用该原则归约原序列，可将其长度由$10^8$减少到$10$项。

接下来穷举或贪心都可得最终结果$25044905874565165$。

n=10**8
mod=10**9+7
s=t=0
a=[0]

for i in range(n-1):
    s=(s*s+45)%mod
    t+=s
    a.append(s)
    while len(a)>=3 and a[-2]>=a[-1] and a[-2]>=a[-3]:
        d=a[-1]+a[-3]-a[-2]
        a.pop()
        a.pop()
        a.pop()
        a.append(d)

x,y,z,d=0,len(a)-1,1,0
while x<=y:
    if a[x]>a[y]:
        d+=a[x]*z
        x+=1
    else:
        d+=a[y]*z
        y-=1
    z=-z

print((t+d)//2)