解題說明
Stone Game IX
題目描述： Alice 和 Bob 輪流從石子堆中取石子（Alice 先手）。每次取一顆石子後，若已取石子的總和能被 3 整除，則取該石子的玩家輸。若所有石子都取完仍無人輸，則 Alice 輸。判斷 Alice 是否能在雙方都最優策略下獲勝。
解題思路： 關鍵觀察是我們只需關注每顆石子對 3 的餘數（0、1、2）。設 c0、c1、c2 分別為餘數為 0、1、2 的石子數量。
- 餘數為 0 的石子不改變總和的餘數，但會交換先後手的角色。
- Alice 第一步必須選餘數 1 或餘數 2 的石子（選 0 會立即輸）。
- 若 Alice 選了餘數 1 的石子，之後雙方為了避免總和被 3 整除，取石子順序為 1,1,2,1,2,...。反之選餘數 2 則為 2,2,1,2,1,...。
- 若 c1 == 0 且 c2 == 0，Alice 無法取石子（或取 0 直接輸），Alice 輸。
- 若 c1 == 0 或 c2 == 0（但非兩者皆 0），只有一種選擇。此時若非零方的數量 > 2 且 c0 為偶數，Alice 才能贏。
- 若 c1 和 c2 都不為 0，Alice 選差值較小的那方起手。若 c0 為偶數，只要 c1 != c2 Alice 就贏。若 c0 為奇數，需要 |c1 - c2| > 2 Alice 才能贏。
C++ 解法
複雜度分析
時間複雜度：O(n) — 遍歷一次陣列統計每個餘數的數量。
空間複雜度：O(1) — 只使用三個計數變數。
虛擬碼
1. Count stones by remainder mod 3: c0, c1, c2. 2. If c1 == 0 and c2 == 0, return false (Alice loses). 3. If c1 == 0, return c2 > 2 and c0 is even. 4. If c2 == 0, return c1 > 2 and c0 is even. 5. If c0 is even, return c1 != c2. 6. If c0 is odd, return |c1 - c2| > 2.
其他解法
-
模擬博弈法：用遞迴或動態規劃模擬所有可能的取石子順序，判斷勝負。時間複雜度 O(n!) 或使用記憶化搜索優化到 O(c0 * c1 * c2)，但仍遠不如數學解法高效。
-
分類討論窮舉法：枚舉 Alice 第一步選擇（mod 1 或 mod 2），然後貪心模擬後續流程。每種起始選擇模擬 O(n) 次操作，總共 O(n)。這種方法更直觀但實現較冗長。
延伸思考
- 如果不是兩人博弈而是三人博弈，規則如何變化？分析複雜度會如何增加？
- 若將「被 3 整除則輸」改為「被 K 整除則輸」，解題思路需要哪些調整？
- 若石子不是一次取一顆，而是可以取 1 到 M 顆，問題的性質會如何改變？