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 給出答案。
--
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 給出答案。
--
All Comments