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)。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 129.2.129.154