*[[Problem 477:http://projecteuler.net/problem=477]] 「数列ゲーム」 [#b6326f65]

数列ゲームは一列に書かれた '''N''' 個の数からなる数列 '''S''' から始まる.

2人のプレーヤーが交互にターンを交代する. ターンが来ると, プレーヤーは数列に存在する先頭か末尾の数のどちらかを選択し取り除く.

プレーヤーの得点は取り除いた全ての数の合計となる. それぞれのプレーヤーは自身の得点の合計を最大化するよう努める.

'''N''' = 4, そして '''S''' = {1, 2, 10, 3} のとき, 以下のようにそれぞれのプレーヤーは自身の得点を最大にしていく:

- プレーヤー 1: 先頭の数を取り除く (1)
- プレーヤー 2: 残りの数列から末尾の数を取り除く (3)
- プレーヤー 1: 残りの数列から末尾の数を取り除く (10)
- プレーヤー 2: 残りの数を取り除く (2)

プレーヤー 1 の得点は 1 + 10 = 11 となる.

下記のように定義された数列 '''S''' = {'''s'''&sub{1};, '''s'''&sub{2};, ..., '''s'''&sub{'''N'''};} においてプレーヤー双方が最適な戦略に従った時のプレーヤー 1 の得点を '''F'''('''N''') としよう:

- '''s'''&sub{1}; = 0
- '''s'''&sub{'''i'''+1}; = ('''s'''&sub{'''i'''};&sup{2}; + 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&sup{4};) = 2495838522951 が与えられている.

'''F'''(10&sup{8};) を求めよ.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS