ProjectEuler 391 Hopping Game - 拼圖

391. Hopping Game

http://projecteuler.net/problem=391


使 s_k 為將 0 到 k 的數字以二進制表示時 1 的數量。

舉例來說，將 0 到 5 以二進制表示時，我們得到 0, 1, 10, 11, 100, 101

一共有 7 個 1，故 s_5 = 7。

而數列 S = { s_k : k≧0 }，起始幾項為 {0, 1, 2, 4, 5, 7, 9, 12, ...}


有個遊戲是兩人玩的，遊戲開始前會先選擇一個數字 n，且有個計數器 c 起始值為 0。

輪到某玩家的回合時，該玩家選擇 1 到 n（含）的其中一個數字且將該數加至計數器上

而 c 的值一定要是 S 的其中一位成員。

如果怎麼選擇並加至計數器中皆無法達成條件，該玩家輸掉這遊戲。


這有個例子：

起初選擇 n = 5，c = 0。

玩家 1 選擇 4，所以 c 為 0 + 4 = 4。

玩家 2 選擇 5，所以 c 為 4 + 5 = 9。

玩家 1 選擇 3，所以 c 為 9 + 3 = 12。

以此類推

記得，c 一定屬於 S，且每位玩家都可以將至多 n 的數加到 c 上。


使 M(n) 為玩家 1 在第一回合中，為了使自己一定會獲得勝利，所能選擇最大的數。

如果怎麼選都做不到，則 M(n) = 0。

舉例，M(2) = 2、M(7) = 1、M(20) = 4。


已知 Σ(M(n))^3 = 8150，當 1 ≦ n ≦ 20。

請求出 Σ(M(n))^3，當 1 ≦ n ≦ 1000。

--