整理的演算法模板合集： ACM模板

點我看演算法全家桶系列！！！

實際上是一個全新的精煉模板整合計劃

我更愿稱之為組合游戲hhh

0x00 公平組合游戲ICG

若一個游戲滿足：

• 由兩名玩家交替行動

• 在游戲行程的任意時刻，可以執行的合法行動與輪到哪名玩家無關

• 游戲中的同一個狀態不可能多次抵達，游戲以玩家無法行動為結束，且游戲一定會在有限步后以非平局結束

則稱該游戲為一個公平組合游戲，

例如 Nim 博弈屬于公平組合游戲，而普通的棋類游戲，比如圍棋，就不是公平組合游戲，因為圍棋交戰雙方分別只能落黑子和白子，勝負判定也比較復雜，不滿足條件2和條件3，

0x01 有向圖游戲（博弈圖）

給定一個有向無環圖，圖中有一個唯一的起點，在起點上放有一枚棋子，兩名玩家交替地把這枚棋子沿有向邊進行移動，每次可以移動一步，無法移動者判負，該游戲被稱為有向圖游戲，

任何一個公平組合游戲都可以轉化為有向圖游戲，具體方法是，把每個局面看成圖中的一個節點，并且從每個局面向沿著合法行動能夠到達的下一個局面連有向邊， 轉化為有向圖游戲，也稱繪制了它的博弈狀態圖（簡稱博弈圖或游戲圖），

這樣，對于組合游戲中的每一次對弈（每一局游戲），我們都可以將其抽象成游戲圖中的一條從某一頂點到出度為 0 0 0 的點的路徑，

組合游戲向圖的轉化，并不單單只是為了尋找一種對應關系，它可以幫助我們淡化游戲的實際背景，強化游戲的數學模型，更加突出游戲 的數學本質，

0x02 先手必勝和先手必敗

• 先手必勝狀態 ： 先手行動以后，可以讓剩余的狀態變成必敗狀態 留給對手（下一步是對手（后手）的局面），

• 先手必敗狀態 ： 不管怎么操作，都達不到必敗狀態，換句話說，如果無論怎么行動都只能達到一個先手必勝狀態留給對手，那么對手（后手）必勝，先手必敗，

簡化一下就是：

• 先手必勝狀態：可以走到某一個必敗狀態

• 先手必敗狀態：走不到任何一個必敗狀態

因為我們當前走到的狀態是送給對手的狀態hhh

通常先手是 A l i c e \tt Alice Alice ，后手是 B o b \tt Bob Bob ，

定理：

定理 2.1： 沒有后繼狀態的狀態是必敗狀態，

定理 2.2： 一個狀態是必勝狀態當且僅當存在至少一個必敗狀態為它的后繼狀態，

定理 2.3： 一個狀態是必敗狀態當且僅當它的所有后繼狀態均為必勝狀態，

如果博弈圖是一個有向無環圖，則通過這三個定理，我們可以在繪出博弈圖的情況下用 O ( N + M ) O(N+M) O(N+M) 的時間（其中 N N N 為狀態種數， M M M 為邊數）得出每個狀態是必勝狀態還是必敗狀態，

0x03 必勝點和必敗點

必敗點(P點) 前一個(previous player)選手將取勝的點稱為必敗點

必勝點(N點) 下一個(next player)選手將取勝的點稱為必勝點

(1) 所有終結點是必敗點（P點）

(2) 從任何必勝點（N點）操作，至少有一種方法可以進入必敗點（P點）

(3)無論如何操作， 從必敗點（P點）都只能進入必勝點（N點）

0x04 有向圖的核

給定一張DAG圖 < V , E > <V,E> <V,E>，如果 V V V 的一個點集 S S S 滿足：

• S S S 是獨立集（集合內的點互不相通）

• 集合 V ? S V-S V?S 中的點都可以通過一步到達集合 S S S 中的點（ V ? S V-S V?S 指 S S S 在 V V V 中的補集）

則稱 S S S 是圖 V V V 的一個核，

結論： 核內節點對應 SG 組合游戲的必敗態

因為 Alice 當前的棋子在 S S S 中，由于 S S S 是獨立集，也就意味著 Alice 只能將棋子從 S S S 移動到 V ? S V-S V?S

而 Bob又可以通過一步移動將棋子從 V ? S V-S V?S 移動到了 S S S，這樣 Alice 就好像是被支配了一樣，被迫把棋子移動到了沒有出度的必敗節點，Alice 必敗，Bob必勝！

0x10 幾個經典組合游戲

0x11 尼姆游戲 N i m G a m e \tt Nim\ Game Nim Game

題目大意

給定 N N N 堆物品，第i堆物品有Ai個，兩名玩家輪流行動，每次可以任選一堆，取走任意多個物品，可把一堆取光，但不能不取，取走最后一件物品者獲勝，兩人都采取最優策略，問先手是否必勝，

我們把這種游戲稱為 Nim 博弈，把游戲程序中面臨的狀態稱為局面，整局游戲第一個行動的稱為先手，第二個行動的稱為后手，若在某一局面下無論采取何種行動，都會輸掉游戲，則稱該局面必敗，

所謂采取最優策略是指，若在某一局面下存在某種行動，使得行動后對手面臨必敗局面，則優先采取該行動，同時，這樣的局面被稱為必勝，我們討論的博弈問題一般都只考慮理想情況，即兩人均無失誤，都采取最優策略行動時游戲的結果，

Nim 博弈不存在平局，只有先手必勝和先手必敗兩種情況，

Solution

通過繪制博弈圖，可以在 O ( Π i = 1 n a i ) \mathcal O(\Pi _{i=1}^n\ a_i) O(Πi=1n? ai?) 的時間內求出該局是否先手必贏 but，這個時間復雜度太高了

結論：定義 Nim 和為 a 1 ⊕ a 2 ⊕ . . . ⊕ a n a_1\oplus a_2\oplus...\oplus a_n a1?⊕a2?⊕...⊕an?，

當且僅當 N i m Nim Nim 和為 0 0 0 時，該狀態為先手必敗狀態 否則該狀態為先手必勝狀態

考慮證明：

我們只需要證明 a 1 ⊕ a 2 ⊕ . . . ⊕ a n =? 0 a_1\oplus a_2\oplus...\oplus a_n\not=0 a1?⊕a2?⊕...⊕an??=0 是先手必勝狀態， a 1 ⊕ a 2 ⊕ . . . ⊕ a n = 0 a_1\oplus a_2\oplus...\oplus a_n=0 a1?⊕a2?⊕...⊕an?=0 是先手必敗狀態即可，

我們可以從先手必敗和先手必勝狀態的定義出發，也就是說我們只需要證明下面的三個定理即可（博弈論結論證明都是朝著這個方向證明的）：

定理1： 沒有后繼狀態的狀態為必敗狀態

定理2： 對于 a 1 ⊕ a 2 ⊕ . . . ⊕ a n =? 0 a_1\oplus a_2\oplus...\oplus a_n\not=0 a1?⊕a2?⊕...⊕an??=0 的局面，一定存在某種移動使得 a 1 ⊕ a 2 ⊕ . . . ⊕ a n = 0 a_1\oplus a_2\oplus...\oplus a_n=0 a1?⊕a2?⊕...⊕an?=0 （必勝狀態一定能到達一個必敗狀態）

定理3： 對于 a 1 ⊕ a 2 ⊕ . . . ⊕ a n = 0 a_1\oplus a_2\oplus...\oplus a_n=0 a1?⊕a2?⊕...⊕an?=0 的局面，一定不存在某種移動使得 a 1 ⊕ a 2 ⊕ . . . ⊕ a n ≠ 0 a_1\oplus a_2\oplus...\oplus a_n \neq0 a1?⊕a2?⊕...⊕an??=0 （必敗狀態一定不能到達任何必敗狀態）

定理1證明： 沒有后繼狀態的狀態（必敗點）只有一個，即全 0 0 0 局面 此時 a 1 ⊕ a 2 ⊕ . . . ⊕ a n = 0 a_1\oplus a_2\oplus...\oplus a_n=0 a1?⊕a2?⊕...⊕an?=0，定理1得證 □

定理2證明： 我們不妨假設 a 1 ⊕ a 2 ⊕ . . . ⊕ a n = k =? 0 a_1\oplus a_2\oplus...\oplus a_n=k\not=0 a1?⊕a2?⊕...⊕an?=k?=0，如果我們將 a i a_i ai? 改為 a i ′ a_i' ai′? ，則 a i ′ = a i ⊕ k a_i'=a_i\oplus k ai′?=ai?⊕k，

設 k k k 在二進制下最高位的 1 1 1 在第 x x x 位，則一定有奇數個 a i a_i ai? 的二進制下在 x x x 位為 1 1 1（異或運算，相同為 1 1 1 ），

因為 a i ⊕ k = a i ′ < a i a_i\oplus k=a_i'<a_i ai?⊕k=ai′?<ai? ，所以我們就可以從 a i a_i ai? 這堆中拿走 a i ⊕ k = a i ′ a_i\oplus k=a_i' ai?⊕k=ai′? 個石子（ a i > a i ′ a_i>a_i' ai?>ai′?，所以有足夠的石子去拿），則 a i a_i ai? 就變成了 a i ? ( a i ? a i ⊕ k ) = a i ⊕ k = a i ′ a_i-(a_i-a_i\oplus k)=a_i\oplus k=a_i' ai??(ai??ai?⊕k)=ai?⊕k=ai′?

則剩下的 Nim 和為 a 1 ⊕ a 2 ⊕ ? ⊕ a i ⊕ k ⊕ a i + 1 ⊕ ? ⊕ a n = k ⊕ k = 0 a_1\oplus a_2\oplus \cdots \oplus a_i\oplus k\oplus a_{i+1}\oplus\cdots \oplus a_n=k\oplus k=0 a1?⊕a2?⊕?⊕ai?⊕k⊕ai+1?⊕?⊕an?=k⊕k=0，定理2得證 □

定理3證明： 當前狀態為 a 1 ⊕ a 2 ⊕ . . . ⊕ a n = 0 a_1\oplus a_2\oplus...\oplus a_n=0 a1?⊕a2?⊕...⊕an?=0 ，我們僅需證明不管怎么拿，Nim 和都不會為 0 0 0 ，

我們使用反證法：

假設我們從 a i a_i ai? 拿走若干石子變為 a i ′ a_i' ai′? ，使得Nim和變為 0 0 0 ，

則說明存在：

a 1 ⊕ a 2 ⊕ ? ⊕ a i ′ ⊕ a i + 1 ⊕ ? ⊕ a n = 0 a_1\oplus a_2\oplus \cdots \oplus a_i' \oplus a_{i+1}\oplus\cdots \oplus a_n =0 a1?⊕a2?⊕?⊕ai′?⊕ai+1?⊕?⊕an?=0

但我們知道當前狀態 Nim和為 0 0 0，即：

a 1 ⊕ a 2 ⊕ ? ⊕ a i ⊕ a i + 1 ⊕ ? ⊕ a n = 0 a_1\oplus a_2\oplus \cdots \oplus a_i \oplus a_{i+1}\oplus\cdots \oplus a_n =0 a1?⊕a2?⊕?⊕ai?⊕ai+1?⊕?⊕an?=0

兩式異或起來得出 a i = a i ′ a_i=a_i' ai?=ai′? ，很明顯這是在原地轉圈，不是合法的移動，不存在這種走法，定理3得證 □

定理 1 ~ 3 得證，故 a 1 ⊕ a 2 ⊕ . . . ⊕ a n =? 0 a_1\oplus a_2\oplus...\oplus a_n\not=0 a1?⊕a2?⊕...⊕an??=0 是先手必勝狀態， a 1 ⊕ a 2 ⊕ . . . ⊕ a n = 0 a_1\oplus a_2\oplus...\oplus a_n=0 a1?⊕a2?⊕...⊕an?=0 是先手必敗狀態， Nim 游戲解題結論得證，

Code

#include <cstdio>
using namespace std;
int n, x, ans;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &x);
        ans ^= x;
    }
    if(ans == 0) puts("No");
    else puts("Yes");
    return 0;
}

0x12 巴什博弈 B a s h G a m e \tt Bash \ Game Bash Game

有 1 堆石子，總個數是 n ，兩名玩家輪流在石子堆中拿石子，每次至少取 1 個，至多取 m 個，取走最后一個石子的玩家為勝者，判定先手和后手誰勝，

結論

若 ( m + 1 ) ∣ n (m+1)\ |\ n (m+1) ∣ n （整除）則先手必敗 否則先手必勝

考慮證明：

情況一： 當 n ≤ m n\le m n≤m 時，顯然先手獲勝

情況二： 當 n = m + 1 n=m+1 n=m+1 時，先手最多可取走 m m m 個，無論其取走多少個，剩下的后手總能一次取完，

情況三： 若 ( m + 1 ) ∣ n (m+1)|n (m+1)∣n ，假設先手拿走了 x x x 個，那么后手一定可以拿走 ( m + 1 ) ? x (m+1)-x (m+1)?x 個，這樣無論怎么拿剩下的石頭個數都將是 m + 1 m+1 m+1 的倍數，那么最后一次取的時候石頭個數必定還剩下 m + 1 m+1 m+1 個，即情況二，

否則的話，先手可以取走模 m + 1 m+1 m+1 余數個數的石頭 此時轉換為 ( m + 1 ) ∣ n (m+1)|n (m+1)∣n 的局面 送給后手，這樣后手變成了先手，也就就是后手必敗，

Code

可以直接模擬

int main() {
	scanf("%d%d", &n, &m);
    if (n % (m + 1))
        puts("first win");
    else
        puts("second win");

    return 0;
}

也可以轉換成SG 游戲使用 SG 函式 （SG函式見下節）

bool vis[N];
int sg[N];
void SG(int n, int m) {
    for (int i = 0; i <= n; ++i) {
        memset(vis, 0, sizeof(vis));
        for (int j = max(i - m, 0), j < i; ++j)
            vis[sg[j]] = 1;
        for (int j = 0; j <= n; ++j)
            if (!vis[j]) {
                sg[i] = j;
                break;
            }
    }
}
int main() {
	scanf("%d%d", &n, &m);
    SG(n, m);
    puts(sg[n] ? "first win" : "second win");
    return 0;
}

0x13 威佐夫博弈 W y t h o f f G a m e \tt Wythoff\ Game Wythoff Game

Problem A 取石子游戲（POJ 1063）

有兩堆石子，石子數可以不同，兩人輪流取石子，每次可以在一堆中取，或者從兩堆中取走相同個數的石子，數量不限，取走最后一個石頭的人獲勝，判定先手是否必勝，

Solution

一共只有兩堆石子，我們可以把問題放到到二維坐標系上，設 x , y x,y x,y 分別對應兩堆的石子的數量，

模擬發現顯然 ( 0 , 0 ) (0,0) (0,0) 先手必敗，我們將先手必敗節點稱為 奇異節點，

可以發現奇異節點上下左右四個結點，以及右上和右下的兩個結點都不是奇異節點，

也就意味著如果 Alice 不在奇異節點上，那么 Alice 可以通過一步操作到達奇異節點，把奇異結點留給 Bob ，這樣 Bob 必敗，

我們可以發現 ( 1 , 2 ) , ( 3 , 5 ) (1,2),(3,5) (1,2),(3,5) 等等也都是奇異節點，

經過奇異節點的 3 3 3 條直線上的點，都能通過一步到達奇異節點，

發現這就建立起了一個有向圖的核的模型，

考慮引入 Beatty定理

如果兩個無理數 a , b a,b a,b 滿足：

1 a + 1 b = 1 \cfrac{1}{a}+\cfrac{1}{b}=1 a1?+b1?=1

那么對于兩個集合 A , B A,B A,B：

A = { ? n a ? } , B = { ? n b ? } , n ∈ Z A=\begin{Bmatrix}\lfloor na\rfloor \end{Bmatrix},B=\begin{Bmatrix}\lfloor nb\rfloor \end{Bmatrix},n\in Z A={?na??},B={?nb??},n∈Z

有下面兩個結論：

A ∩ B = ? , A ∪ B = N + A\cap B=\varnothing,A\cup B=N^+ A∩B=?,A∪B=N+ （結論證明）

打表 發現 B i ? A i = i B_i?A_i=i Bi??Ai?=i

可得 b = a + 1 b=a+1 b=a+1 ，帶入 1 a + 1 b = 1 \cfrac{1}{a}+\cfrac{1}{b}=1 a1?+b1?=1 解得 a = 5 + 1 2 , b = 3 ? 5 2 a=\cfrac{\sqrt{5}+1}{2},b=\cfrac{3-\sqrt{5}}{2} a=25 ?+1?,b=23?5 ??

最終得出威佐夫博弈結論：假設兩堆石子為 ( a , b ) (a,b) (a,b)（其中 a < b a<b a<b ）

那么先手必敗，當且僅當 ( b ? a ) × ( 5 + 1 ) 2 = a (b-a)\times \cfrac{(\sqrt{5}+1)}{2}=a (b?a)×2(5 ?+1)?=a

其中的 ( 5 + 1 ) 2 \cfrac{(\sqrt{5}+1)}{2} 2(5 ?+1)? 實際就是黃金分割數 1.618 1.618 1.618，細思極恐，細思極恐…

Code

int main() {
	scanf("%d%d", &n, &m);
    if (a > b)
        swap(a, b);
    int ans = (b - a) * ((1.0 + sqrt(5.0)) / 2.0);
    if (ans == a)
        puts("0");
    else
        puts("1");
    return 0;
}

Problem A Game of Taking Stones（2017 ACM ICPC dalian C）

給你兩個石堆的石頭數量 a , b a,b a,b，兩個人輪流拿，兩人輪流從任意一堆取至少一個或者從兩堆取同樣多的物品，問你先手獲勝還是后手勝，

a , b ≤ 1 0 100 a,b\le10^{100} a,b≤10100

威佐夫博弈模板題，但是資料開到了 1 0 100 10^{100} 10100，普通的C++高精會炸，所以直接用Java就行了（而且Java比C++高精好寫多了 ~ ）

我們直接用 Java 二分求出 5 \sqrt{5} 5 ?，設 b > a b>a b>a 計算 ( b ? a ) × ( 5 + 1 ) 2 \cfrac{(b-a)\times (\sqrt{5}+1)}{2} 2(b?a)×(5 ?+1)? 即可，

Code

import java.math.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        BigDecimal one = BigDecimal.valueOf(1);
        BigDecimal two = BigDecimal.valueOf(2), five = BigDecimal.valueOf(5);
        BigDecimal t = one.add(sqrt(five, 500)).divide(two);
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            BigDecimal a, b, tmp = null;
            a = sc.nextBigDecimal();
            b = sc.nextBigDecimal();

            if (a.compareTo(b) > 0) {
                tmp = a;
                a = b;
                b = tmp;
            }

            if (b.subtract(a).multiply(t).setScale(0, BigDecimal.ROUND_DOWN).equals(a)) {
                System.out.println(0);
            } else
                System.out.println(1);

        }

        sc.close();
    }

    private static BigDecimal sqrt(BigDecimal x, int n) {
        BigDecimal l = BigDecimal.ZERO, r = x, mid;
        BigDecimal two = BigDecimal.valueOf(2);

        for (int i = 0; i <= n; i++) {
            mid = l.add(r).divide(two);

            if (mid.pow(2).compareTo(x) <= 0)
                l = mid;
            else
                r = mid;
        }

        return l;
    }
}

0x14 斐波那契博弈 F i b o n a c c i G a m e \tt Fibonacci\ Game Fibonacci Game

待更…

0x20 SG函式

0x21 前置知識： M e x Mex Mex 運算

設 S S S 表示一個非負整數集合，定義 m e x ( S ) mex(S) mex(S) 為求出不屬于集合S的最小非負整數的運算，即：

m e x ( S ) = m i n { x } mex(S) = min\{x\} mex(S)=min{x}， x x x 屬于自然數，且 x x x 不屬于 S S S ，

0x22 SG函式

SG函式是對游戲圖中每一個節點的評估函式，

規定游戲終點的 SG 函式值定為 0 0 0，即 S G ( 終 點 ) = 0 SG(終點)=0 SG(終點)=0，

在有向圖游戲中（任何一個博弈都可以轉換為一個有向圖游戲），對于每個節點 x x x （局面），設從 x x x 出發共有 k k k 條有向邊（合法的操作），分別到達節點 y 1 , y 2 , … , y k y_1, y_2, …, y_k y1?,y2?,…,yk?（下一個局面） ，定義 S G ( x ) SG(x) SG(x) 為 x x x 的后繼節點（注意只是一層的后繼結點） y 1 , y 2 , … , y k y_1, y_2, …, y_k y1?,y2?,…,yk? 的 S G SG SG 函式值構成的集合再執行 m e x ( S ) mex(S) mex(S) 運算的結果，即：

S G ( x ) = m e x ( { S G ( y 1 ) , S G ( y 2 ) , … , S G ( y k ) } ) SG(x) = mex(\{SG(y1), SG(y2), …, SG(yk)\}) SG(x)=mex({SG(y1),SG(y2),…,SG(yk)})

如 圖20.1 所示：

圖20.1

%2

特別地，整個有向圖游戲 G G G 的 S G SG SG 函式值被定義為有向圖游戲起點 s s s 的 S G SG SG 函式值，即 S G ( G ) = S G ( s ) SG(G) = SG(s) SG(G)=SG(s) ，

我們發現若 S G ( x ) = 0 SG(x)=0 SG(x)=0 則為必敗狀態，若 S G ( x ) =? 0 SG(x)\not= 0 SG(x)?=0，則為必勝狀態，（若非零說明這個點直接指向了 0 0 0，也就意味著可以到達必敗狀態，是必勝狀態）

0x23 SG 函式的性質

兩個SG函式的性質：

（1）對于任意的局面，如果它的 S G SG SG 值為 0 0 0 ，那么它的任何一個后
繼局面的SG值不為 0 0 0 ，

（2）對于任意的局面，如果它的 S G SG SG 值不為 0 0 0 ，那么它一定有一個
后繼局面的 S G SG SG 值為 0 0 0 ，

SG（ S p r a g u e ? G r u n d y \tt Sprague-Grundy Sprague?Grundy）定理 ：所有一般勝利下的公平組合游戲都能轉化成尼姆數表達的尼姆堆博弈，一個博弈的 尼姆值 定義為這個博弈的等價尼姆數，即：對于當前游戲 X X X，它可以拆分成若干個子游戲 x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1?,x2?,...,xn? 那么 S G ( X ) = S G ( x 1 ) ⊕ S G ( x 2 ) ⊕ . . . ⊕ S G ( x n ) SG(X)=SG(x_1)\oplus SG(x_2)\oplus...\oplus SG(x_n) SG(X)=SG(x1?)⊕SG(x2?)⊕...⊕SG(xn?)

對于由 n n n 個有向圖游戲組成的組合游戲 設它們的起點分別為 s 1 , s 2 , . . . , s n s_1,s_2,...,s_n s1?,s2?,...,sn?（好多個起點，有好多個博弈圖，也就是有好多個 圖20.1 ） ，則當且僅當 S G ( s 1 ) ⊕ S G ( s 2 ) ⊕ . . . ⊕ S G ( s n ) =? 0 SG(s_1)\oplus SG(s_2)\oplus...\oplus SG(s_n)\not=0 SG(s1?)⊕SG(s2?)⊕...⊕SG(sn?)?=0 時，這個游戲為先手必勝 ，

也就意味著，我們將原本需要考慮博弈圖的所有點，復雜度較高，但是我們通過SG函式，變成了只需要考慮起點即可，

證明方法類似尼姆游戲，略，

0x24 轉換為 Nim 游戲

事實上，每一個簡單SG-組合游戲都可以完全等效成一堆數目為 K K K 的石子（Nim 游戲），其中 K K K 為該簡單游戲的 S G SG SG 函式值，這樣的等效是充要的，

定義游戲的和： 考慮任意多個同時進行的SG-組合游戲，這些SG-組合游
戲的和是這樣一個SG-組合游戲，在它進行的程序中，游戲者可以任意
挑選其中的一個 單一游戲 進行決策，最終，沒有辦法進行決策的人輸，

定理 23.1： 在我們每次只能進行一步操作的情況下，對于任何的游戲的和，我們若將其中的任一單一SG-組合游戲換成數目為它的SG值的一堆石子， 該單一SG-組合游戲的規則變成取石子游戲的規則（可以任意取，甚至 取完），則游戲的和的勝負情況不變，

這個定理告訴我們，在考慮游戲的和時，每一個單一游戲的具體細節是可以被忽略的，我們所關心的只是SG函式值，所以我們可以將組成它的所有子游戲全部換成相應數目的一堆石子，這樣，所有的游戲的和都等價成一個 Nim 游戲，

0x24 有向圖游戲的和

設 G 1 , G 2 , … , G m G_1, G_2, …, G_m G1?,G2?,…,Gm? 是 m m m 個有向圖游戲，定義有向圖游戲 G G G ，它的行動規則是任選某個有向圖游戲 G i G_i Gi? ，并在 G i G_i Gi? 上行動一步， G G G 被稱為有向圖游戲 G 1 , G 2 , … , G m G_1, G_2, …, G_m G1?,G2?,…,Gm?的和，

有向圖游戲的和的 S G SG SG 函式值等于它包含的各個子游戲 S G SG SG 函式值的異或和，即：

S G ( G ) = S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ … ⊕ S G ( G m ) SG(G) = SG(G_1) \oplus SG(G_2)\oplus …\oplus SG(G_m) SG(G)=SG(G1?)⊕SG(G2?)⊕…⊕SG(Gm?)

定理22.1： 有向圖游戲的某個局面必勝，當且僅當該局面對應節點的SG函式值大于0，

定理22.2： 有向圖游戲的某個局面必敗，當且僅當該局面對應節點的SG函式值等于0，

我們只需要判斷一下 S G ( G ) SG(G) SG(G) 即可，

Problem A 集合- Nim游戲（ AcWing 893）

給定 n n n 堆石子以及一個由 k k k 個不同正整數構成的數字集合 S S S ，

現在有兩位玩家輪流操作，每次操作可以從任意一堆石子中拿取石子，每次拿取的石子數量必須包含于集合 S S S ，最后無法進行操作的人視為失敗，

問如果兩人都采用最優策略，先手是否必勝，

每一堆輸入的石子數就是每一堆的起點，答案就是所有起點的 Nim 和

假設某一堆有 10 10 10 個石子， S = { 2 , 5 } S=\{2,5\} S={2,5} 那么博弈圖就是從 10 10 10 開始連邊，如圖20.1 所示，

圖20.2

本題的連邊方式就是從集合 S S S 中選擇一個數往下走（取走這么多數，往下搜 x ? s u m x-sum x?sum）

我們直接記憶化搜索sg函式即可

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <cstring>

using namespace std;
const int N = 507, M = 50007;
typedef long long ll;
typedef int itn;

itn n, m;
int a[N];
itn s[N], f[M];

int sg(int x)//記憶化搜索
{
    if(f[x] != -1) return f[x];
    
    unordered_set<int>S;
    for(int i = 1; i <= m; ++ i) {
        itn sum = s[i];
        if(x >= sum) S.insert(sg(x - sum));
    }
    for(int i = 0; ; ++ i) {
        if(!S.count(i))
        return f[x] = i;
    }
}

int main()
{
    scanf("%d", &m);
    for(int i = 1; i <= m; ++ i) {// m 個起點
        scanf("%d", &s[i]);
    }
    int res = 0;
    scanf("%d", &n);
    memset(f, -1, sizeof f);
    for(int i = 1; i <= n; ++ i) {
        int x;
        scanf("%d", &x);
        res ^= sg(x);
    }
    
    if(res == 0) puts("No");
    else puts("Yes");
    return 0;
}

以下為待更內容，預計將在 2021/2/21 前更完 (●ˇ?ˇ●)

0x30 SG游戲及其拓展變形

0x 31 Anti-SG 游戲（走完最后一步者輸）

Anti-Nim游戲

有 n n n 堆石子，兩個人可以從任意一堆石子中拿任意多個石子(不能不拿)，拿走最后一個石子的人失敗，問誰會勝利

看上去好像顛覆了SG游戲的規則，連勝利的條件都反了這怎么玩？

先給出結論

先手必勝當且僅當：

（1） ? \forall ? 所有堆的石子數都為 1 1 1 且游戲的SG值為 0 0 0 ，

（2） ? \exist ? 有些堆的石子數大于 1 1 1 且游戲的SG值不為 0 0 0 ，

考慮證明：

游戲大概可以被分為3種情況

• 每堆只有一個石子

當異或值（SG值）為 0 0 0 時（有奇數堆），先手必勝
當異或值（SG值）不為 0 0 0 時（有偶數堆），先手必敗

• 只有一堆石子數大于1，先手必勝

經過分析不難發現，先手可以對數量大于1的那堆石子下手腳，從而構造出后手必敗的狀態

存在至少兩堆石子數大于1
當異或和為0時，先手必敗
當異或和不為0時，先手必敗
這一步的結論與Nim游戲非常相似，同時它們的證明也非常相似，大概就是從異或和為0的狀態無論怎樣都會變為異或和不為0的狀態，反過來從異或和不為0的狀態總有一步能到達異或和為0的狀態

0x32 SJ定理

0x33 Multi-SG游戲（可以將一堆石子分成多堆）

0x34 Every-SG游戲（每一個可以移動的棋子都要移動）

0x35翻硬幣游戲

0x36 無向圖刪邊游戲

0x40 經典組合游戲拓展

0x41 巴什博奕的擴展——k倍動態減法游戲

0x42 尼姆博弈的三種擴展

0x50 尋找必敗態解題

0x60 不平等博弈問題

0x70 更多例題

Problem A Euclid’s Game（POJ 1063 ）

給定兩個正整數 a , b a,b a,b，每次操作，可以將大的數減掉小的數的整數倍，當一個數變為 0 0 0 的時候結束，先將其中一個數減為 0 0 0 的獲勝，Stan先手，問誰能贏，

Solution

把問題轉化成我們熟悉的模型，相當于有一排石子堆，必須把前面的石子堆取完了才能取后面的，取最后一個石子的人贏，問誰能贏

• 博弈論知識匯總

• 博弈論合集（博弈）

• 博弈論全家桶

• 博弈論題目總結（一）——簡單組合游戲

• 博弈論題目總結（二）——SG組合游戲及變形

• 博弈論入門之威佐夫博弈

• 博弈論進階之Anti-SG游戲與SJ定理

• 博弈論總結

• 《淺談如何解決不平等博弈問題》 方展鵬

• 《從“k倍動態減法游戲”出發探究一類組合游戲問題》曹欽翔

• 《組合游戲略述——淺談SG游戲的若干拓展及變形》賈志豪

• acm中的一些博弈論知識

• ACM-ICPC中博弈論的一些小小總結

• 尋找必敗態——一類博弈問題的快速解法

• 運籌學基礎教程（第二版）第9章 對策（博弈）論.ppt