Sprague Grundy Theorem

Nim

Có nhiều đống, mỗi lượt chọn một đống và bỏ đi một số viên dương. Gọi $X = a_1 \oplus a_2 \oplus \dots \oplus a_n$. Người đi trước thua khi và chỉ khi $X = 0$.

• Từ $X = 0$, đổi một đống $a_i$ thành $a_i' \ne a_i$ thì $X$ đổi thành $a_i \oplus a_i' \ne 0$.
• Từ $X \ne 0$, lấy bit cao nhất của $X$; có đống $a_i$ chứa bit đó, và $a_i \oplus X < a_i$. Hạ đống ấy xuống $a_i \oplus X$ thì tổng XOR về 0.

Hai tính chất này cùng trạng thái cuối (mọi đống bằng 0, $X = 0$, thua) là đủ để quy nạp.

Trong hình, mỗi cột bit có số chữ 1 chẵn thì XOR bằng 0. Bấm Đi nước thắng để xem cách đưa XOR về 0.

Ví dụNước Đi Cuối Cùng

Đề. Nhiều ván Nim, tổng số đống tới $2 \cdot 10^5$, mỗi đống tới $10^9$. In first nếu người đi trước thắng, ngược lại second.

Lời giải. Tính tổng XOR của các đống.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll t, n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n;
        ll x = 0;
        for (ll i = 1; i <= n; i++) {
            ll a;
            cin >> a;
            x ^= a;
        }
        cout << (x ? "first" : "second") << '\n';
    }
}

ChạyInput3
3
2 5 7
4
1 4 6 8
1
9

Outputsecond
first
first

Số Grundy

$\operatorname{mex}$ của một tập là số tự nhiên nhỏ nhất không thuộc tập. Số Grundy định nghĩa bởi

Trạng thái không còn nước đi có $g = 0$. Đống Nim cỡ $a$ có $g = a$: từ nó đi được tới mọi cỡ nhỏ hơn.

Định lý Sprague-Grundy: trạng thái $s$ tương đương đống Nim cỡ $g(s)$. Từ $s$ đi được tới trạng thái có Grundy bằng mọi số nhỏ hơn $g(s)$; còn nước tới trạng thái có Grundy lớn hơn thì đối thủ luôn đi tiếp được về đúng $g(s)$. Vì vậy tổng của nhiều trò con độc lập chơi như Nim trên các Grundy:

Tính $g$ theo thứ tự ngược nước đi: trạng thái nhỏ trước, hoặc DFS có ghi nhớ trên DAG. Trạng thái có $d$ nước đi thì $g \le d$, nên mảng đánh dấu cho mex chỉ cần $d + 1$ ô.

Ví dụBộ Luật Chung

Đề. Nhiều bộ luật tới khi gặp 0. Bộ luật là tập $S$ gồm $k \le 100$ lượng được lấy. Mỗi vị trí gồm tối đa 100 đống cỡ tới $10^4$; mỗi lượt lấy đúng $d \in S$ viên từ một đống. In W hoặc L cho từng vị trí.

Lời giải. Mỗi vị trí là tổng các đống độc lập, nên chỉ cần Grundy $g(x)$ của một đống cỡ $x$ rồi XOR. $g(x)$ là mex của các $g(x - d)$ với $d \in S$, $d \le x$.

Bước 1: bảng Grundy cho mỗi bộ luật. Tính từ nhỏ tới lớn vì $g(x)$ chỉ phụ thuộc các giá trị nhỏ hơn. Có $k$ nước đi nên $g(x) \le k$: mảng seen chỉ cần $k + 1$ ô và phải xóa trước mỗi $x$.

for (int x = 0; x <= 10000; x++) {
    for (int v = 0; v <= k; v++) seen[v] = 0;
    for (int i = 0; i < k; i++)
        if (s[i] <= x) seen[g[x - s[i]]] = 1;
    int v = 0;
    while (seen[v]) v++;
    g[x] = v;
}

Bước 2: mỗi vị trí. XOR g[h] của các đống; khác 0 là người đi trước thắng.

for (int i = 1; i <= l; i++) {
    int h;
    cin >> h;
    x ^= g[h];
}
res += x ? 'W' : 'L';

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int H = 1e4 + 5;
int k, m, s[105], g[H];
bool seen[105];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> k && k) {
        for (int i = 0; i < k; i++) cin >> s[i];
        for (int x = 0; x <= 10000; x++) {
            for (int v = 0; v <= k; v++) seen[v] = 0;
            for (int i = 0; i < k; i++)
                if (s[i] <= x) seen[g[x - s[i]]] = 1;
            int v = 0;
            while (seen[v]) v++;
            g[x] = v;
        }
        cin >> m;
        string res;
        for (int j = 1; j <= m; j++) {
            int l, x = 0;
            cin >> l;
            for (int i = 1; i <= l; i++) {
                int h;
                cin >> h;
                x ^= g[h];
            }
            res += x ? 'W' : 'L';
        }
        cout << res << '\n';
    }
}

+14 dòngChạyInput3
1 3 4
4
1 2
2 1 2
2 3 4
3 2 2 2
2
2 5
3
1 1
1 2
2 2 2
0

OutputLWWL
LWL

Mỗi bộ luật $10^4 \cdot k = 10^6$ phép.

Tìm quy luật

Hình tính từng $G(n)$ là mex của các $G$ sau một nước đi (màu xanh). Đổi tập nước đi để tìm chu kỳ.

Trạng thái quá lớn để tính hết thì viết brute force in $g(0), g(1), \dots$ rồi đoán dạng: tuần hoàn ($a \bmod 4$ khi lấy 1 đến 3 viên), theo cấu trúc số học, hay bằng một đại lượng khác.

Chứng minh thường là chỉ ra trò đó chính là Nim trên đại lượng ấy: mỗi nước làm đại lượng giảm, và giảm được đúng mọi lượng dương.

Ví dụHạ Số Bằng Ước

Đề. $N \le 10^5$ số $A_i \in [2, 10^5]$. Mỗi lượt chọn một số và thay bằng một ước dương nhỏ hơn nó. Ai không đi được thì thua; Anna đi trước.

Lời giải. Gọi $\Omega(A)$ là số thừa số nguyên tố của $A$ tính cả bội. Ước nhỏ hơn của $A$ là $A$ bỏ đi một số dương thừa số nguyên tố, và bỏ được bất kỳ số lượng nào từ 1 tới $\Omega(A)$ (bỏ hết được 1, cũng là ước hợp lệ). Đúng là bốc một số dương viên từ đống cỡ $\Omega(A)$: mỗi số là một đống Nim.

Bước 1: sàng ước nguyên tố nhỏ nhất. Với mỗi số nguyên tố $i$, gán $i$ cho mọi bội chưa có ước nhỏ hơn.

for (int i = 2; i < V; i++)
    if (!spf[i])
        for (int j = i; j < V; j += i)
            if (!spf[j]) spf[j] = i;

Bước 2: tính $\Omega$. Bỏ một thừa số nguyên tố thì $\Omega$ giảm 1. Duyệt $i$ tăng dần nên omega[i / spf[i]] đã có.

for (int i = 2; i < V; i++) omega[i] = omega[i / spf[i]] + 1;

Bước 3: XOR các omega[a]; khác 0 là Anna thắng.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int V = 1e5 + 5;
int n, spf[V], omega[V];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 2; i < V; i++)
        if (!spf[i])
            for (int j = i; j < V; j += i)
                if (!spf[j]) spf[j] = i;
    for (int i = 2; i < V; i++) omega[i] = omega[i / spf[i]] + 1;
    cin >> n;
    int x = 0;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        x ^= omega[a];
    }
    cout << (x ? "Anna" : "Bruno") << '\n';
}

ChạyInput6
2 4 6 8 9 12

OutputAnna

Sàng $O(V \log \log V)$, rồi $O(N)$.

Tách đống

Có trò cho tách một đống thành nhiều đống. Sau nước đó trạng thái là tổng của các đống mới, nên Grundy của nó là XOR Grundy các phần:

Cách nhìn này dùng được cả cho trò trên dải hay bảng: một nước đi chia vùng trống thành các vùng độc lập, mỗi vùng là một trò con.

Ví dụHai Phần Khác Nhau

Đề. $T \le 1000$ test, mỗi test tối đa 100 đống cỡ tới $10^4$. Mỗi lượt tách một đống thành hai đống dương có kích thước khác nhau. Ai không tách được thì thua; Alice đi trước. In Case i: Alice hoặc Case i: Bob.

Lời giải. Tách một đống thành hai đống là chuyển sang tổng của hai trò con, Grundy bằng XOR. Vậy $g(x)$ là mex của $g(a) \oplus g(x - a)$ trên mọi $a < x - a$; điều kiện 2 * a < x loại cách tách thành hai phần bằng nhau. Tính trước một lần cho mọi cỡ tới $10^4$, rồi mỗi test chỉ XOR.

Bước 1: đánh dấu bằng số hiệu. mark[v] = x thay cho mảng đúng/sai: giá trị $v$ đã được đánh dấu cho lần tính hiện tại khi mark[v] == x, nên không cần xóa mảng giữa các $x$. Grundy ở đây nhỏ, dưới $2^{14}$, nên mark cỡ $2^{14}$ chứa đủ mọi giá trị XOR.

for (int x = 1; x < A; x++) {
    for (int a = 1; 2 * a < x; a++) mark[g[a] ^ g[x - a]] = x;
    int v = 0;
    while (mark[v] == x) v++;
    g[x] = v;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int A = 1e4 + 5;
int g[A], mark[1 << 14];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int x = 1; x < A; x++) {
        for (int a = 1; 2 * a < x; a++) mark[g[a] ^ g[x - a]] = x;
        int v = 0;
        while (mark[v] == x) v++;
        g[x] = v;
    }
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        int n, x = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            int a;
            cin >> a;
            x ^= g[a];
        }
        cout << "Case " << tc << ": " << (x ? "Alice" : "Bob") << '\n';
    }
}

ChạyInput4
1
1
2
3 5
3
4 7 10
2
13 18

OutputCase 1: Bob
Case 2: Alice
Case 3: Bob
Case 4: Alice

Tính bảng khoảng $2{,}5 \cdot 10^7$ phép, mỗi test $O(n)$.

Nim bậc thang

Bóng trên các bậc $1..n$, mỗi lượt chuyển một số bóng dương từ bậc $k > 1$ xuống bậc $k - 1$. Chỉ các bậc chẵn quyết định: trò tương đương Nim trên $p_2, p_4, p_6, \dots$

• Chuyển bóng từ bậc chẵn xuống bậc lẻ: bóng đó ra khỏi các đống chẵn, đúng một nước Nim.
• Chuyển bóng từ bậc lẻ xuống bậc chẵn: người kia chuyển đúng số bóng ấy xuống tiếp một bậc, các đống chẵn trở lại như cũ. Nước này không thay đổi được kết quả.

Mẫu này gặp ở nhiều bài: xu trượt về trái trên một dải, các quân không được vượt nhau. Thường phải đổi bài về “khoảng trống giữa các quân” rồi lấy các khoảng ở vị trí xen kẽ.

Ví dụBóng Trên Bậc Thang

Đề. Nhiều ván, tổng số bậc tới $2 \cdot 10^5$, mỗi bậc tới $10^9$ bóng. In first hay second.

Lời giải. XOR số bóng ở các bậc chẵn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll t, n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n;
        ll x = 0;
        for (ll i = 1; i <= n; i++) {
            ll p;
            cin >> p;
            if (i % 2 == 0) x ^= p;
        }
        cout << (x ? "first" : "second") << '\n';
    }
}

ChạyInput2
5
4 3 2 3 1
4
0 5 8 2

Outputsecond
first