ProjectEuler 488 Unbalanced Nim - 拼圖

488. Unbalanced Nim

https://projecteuler.net/problem=488

Alice和Bob每天都快樂地玩Nim遊戲（註）。然而，他們終究是對普通的三堆Nim規則

感到厭煩了。所以，他們增加了一條新的規則：

　- 不能讓任意兩堆棋子數目相同。

我們用數組(a,b,c)來表示遊戲中三堆棋子的數目。

在新的規則下，(2,4,5)對下個玩家來說是一種必敗的組合。

舉例來說：
　- Alice下成(2,4,3)
　- Bob下成(0,4,3)
　- Alice下成(0,2,3)
　- Bob下成(0,2,1)

不像傳統的Nim遊戲，在新規則下，下成(0,1,2)及其重排時，已經無法再做行動。

給定正整數N，我們定義F(N)為所有符合0<a<b<c<N的必敗Nim組合(a,b,c)中a+b+c的和。

例如，F(8) = 42，因為有四種必敗組合符合條件，即(1,3,5)、(1,4,6)、(2,3,6)

以及(2,4,5)。同時亦可驗證F(128) = 496062。

請求出F(10^18)的末九位數。

註：Nim遊戲是一種兩個人玩的回合制數學戰略遊戲。遊戲者輪流從一堆棋子
（或者任何道具）中取走一個或者多個，最後不能再取的就是輸家。當指
定相應數量時，一堆這樣的棋子稱作一個Nim堆。(by wiki)
http://zh.wikipedia.org/zh-tw/%E5%B0%BC%E5%A7%86%E6%B8%B8%E6%88%8F


--