---

Problem 477

---

Number Sequence Game

The number sequence game starts with a sequence S of N numbers written on a line.

Two players alternate turns. At his turn, a player must select and remove either the first or the last number remaining in the sequence.

The player score is the sum of all the numbers he has taken. Each player attempts to maximize his own sum.

If N = 4 and S = {1, 2, 10, 3}, then each player maximizes his score as follows:

• Player 1: removes the first number (1)
• Player 2: removes the last number from the remaining sequence (3)
• Player 1: removes the last number from the remaining sequence (10)
• Player 2: removes the remaining number (2)

Player 1 score is 1 + 10 = 11.

Let F(N) be the score of player 1 if both players follow the optimal strategy for the sequence S = {s₁, s₂, …, s_N} defined as:

• s₁ = 0
• s_i+1 = (s_i² + 45) modulo 1 000 000 007

The sequence begins with S = {0, 45, 2070, 4284945, 753524550, 478107844, 894218625, ……}.

You are given F(2) = 45, F(4) = 4284990, F(100) = 26365463243, F(10⁴) = 2495838522951.

Find F(10⁸).

---

数列游戏

数列游戏从写成一行的N个数组成的序列S开始进行。

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

玩家的得分是他选择的所有数的和。每个玩家都试图最大化自己的得分。

如果N = 4，序列S = {1, 2, 10, 3}，那么每个玩家最大化自己得分的过程如下所示：

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

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

当玩家以按如下方式定义的序列S = {s₁, s₂, …, s_N}开始游戏时，记玩家1的得分为F(N)：

• s₁ = 0
• s_i+1 = (s_i² + 45) modulo 1 000 000 007

序列的开头几项分别为S = {0, 45, 2070, 4284945, 753524550, 478107844, 894218625, ……}.

已知F(2) = 45，F(4) = 4284990，F(100) = 26365463243，F(10⁴) = 2495838522951。

求F(10⁸)。

---