ProjectEuler 366 Stone Game III - 拼圖

366. Stone Game III

http://projecteuler.net/problem=366


有兩個玩家，Anton 和 Bernhard，在玩一場遊戲。

這裡有一堆石頭，共 n 顆。

第一位玩家可以拿掉任何數量的石頭，但不能整堆拿走。

再來，每位玩家拿的石頭數量上限就是「對手最後拿取的數量 X 2」。

誰拿走最後一顆石頭，誰就獲勝。


舉個例子來說，這堆石頭有 5 顆。

如果第一位玩家拿了超過 1 顆石頭(2,3,4)，第二位玩家都能馬上拿走所有石頭並獲勝。

如果第一位玩家拿 1 顆，留下 4 顆，第二位玩家也拿 1 顆，留下 3 顆。

又換第一位玩家，但他至多只能拿 2 顆，所以不論拿 1 或 2 顆，第二位玩家都能獲勝。

所以 n = 5 是第一位玩家的必敗型。

有些必勝型對於第一位玩家有超過一種拿法，比如說 n = 17，可以先拿 1 或 4 顆。


使 M(n) 為必勝型中，第一位玩家第一步可拿取的石頭最大數量，而 M(n) = 0為必敗型。

ΣM(n)，n ≦ 100，答案是 728。

請算出 ΣM(n)，n ≦ 10^18 後再 mod 10^8 給出答案。

--