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
--
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
--
All Comments