ProjectEuler 459 Flipping game - 拼圖

459. Flipping game

http://projecteuler.net/problem=459

翻棋遊戲是一種兩個人玩的遊戲，需要一塊N乘N的棋盤。

每個格子上都有一面黑一面白的黑白棋一枚。

開始時每一枚棋子都是白色朝上。

一個回合代表將一個符合條件的長方形內的所有棋子都翻轉一次，其條件為：

‧長方形的右上角必須是白棋

‧長方形的寬必須是完全平方數n^2 (1, 4, 9, 16, ...)

‧長方形的長必須是三角形數n(n+1)/2 (1, 3, 6, 10, ...)

　●○○●○　●○○●○　●○○●○
　○○○●●　○○○●●　○●●○○
　●○●●○→●○●●○→●●○○●
　○○●○○　○○●○○　○●○●●
　○●●●○　○●●●○　○●●●○

兩個玩家交互輪流，最先把所有白棋翻成黑棋的玩家獲勝。

令W(N)為使用N乘N棋盤時，先手玩家必勝的第一手方法數、並假設雙方均使用最佳策略。

則W(1) = 1、W(2) = 0、W(5) = 8以及W(10^2) = 31395。

在N = 5時，先手玩家必勝的第一手列示如下

　●●●○●　●●●●●　●●●●●　●●●●●
　●●●●●　●●●○●　●●●●●　●●●●●
　●●●●●　●●●●●　●●●○●　●●●●●
　●●●●●　●●●●●　●●●●●　●●●○●
　●●●●●　●●●●●　●●●●●　●●●●●　

　●●●●●　●●●○●　●●●●●　●●●●●
　●●●●●　●●●○●　●●●○●　●●●●●
　●●●●●　●●●○●　●●●○●　●●●○●
　●●●●●　●●●●●　●●●○●　●●●○●
　●●●○●　●●●●●　●●●●●　●●●○●

請求出W(10^6)。

--