366 : 石取りゲーム その3

2人の対局者, アントンとベルンハルトが次のようなゲームをしている. n 個の石が1つの山に積まれている. 初回, 先手は取りうる正の整数個の石を取る, ただし山全体を取ることは出来ない. それから, 対局者はお互いに, 相手が前回取った数の最大2倍まで石を取れる. 最後の石を取ったものが勝者となる.

n=5 の場合をみてみよう. もし先手が2個以上の石を取ったときは後手が残りの石を取ることができる. もし先手が1個石を取れば, 残りは4個となり, 後手も1個取ると, 残りは3個になる. ここで先手は残りの3個の石をすべて取ることはできない, なぜなら 2x1=2, 最大2個の石しか取れないからである. 先手は1個石を取ると残りは2個になる. 後手は残りの2個の石を取ることができ, 勝者となる. つまり石の山が5個のときは後手必勝となる. 先手が勝勢の局面 ( ※ 訳注 : 最善の手を打てば相手がどんな手を打っても勝つことができる局面 ) となる石の取りかたは複数存在することがある. 例えば n=17 の場合, 先手は最初に1個, または4個の石を取ると勝つことができる.

先手が最初のターンで勝勢の局面に持ち込むことができる石の取り方のうち最大の石の数を M(n) と定義し, 後手必勝のときは M(n)=0 としよう.

n≤100 のときの ΣM(n) は 728 となる.

$n≤10^{18}$のときの ΣM(n) を求め,$10^8$を法として答えよ.