形式化题目

给定一张 $N \times M$ 的矩形网格纸（$2 \leqslant N,M \leqslant 200$），两名玩家轮流行动。每次行动任选当前存在的一张纸，沿某一行或某一列的格线把它剪成两部分。首先剪出 $1 \times 1$ 网格纸的玩家获胜。双方均采取最优策略，判断先手必胜（输出 WIN）还是必败（输出 LOSE）。输入包含多组询问，每组给出一对 $N, M$。

正解

思路

从"一张纸的游戏"到"局面 = 若干纸的和"

观察每次操作的性质：一次只选一张纸去剪，其余纸原封不动。也就是说，每张纸都是一个独立的子游戏，整个局面就是这些子游戏的和（Sum of Games）。这正是公平组合游戏的经典场景，直接套用 Sprague-Grundy 定理（SG 定理）：

• 一张纸对应一个 SG 值 $\operatorname{SG}(i, j)$；
• 整个局面（多张纸共存）的 SG 值等于所有纸的 SG 值的按位异或和；
• 先手必败 $\iff$ 初始局面的 SG 异或和为 $0$。

由于初始只有一张 $N \times M$ 的纸，问题化为：求出单张纸的 $\operatorname{SG}(N, M)$，判断它是否为 $0$。

单张纸的 SG 值怎么算

先写朴素定义。一张 $i \times j$ 的纸共有 $(i-1)$ 条横格线与 $(j-1)$ 条竖格线，所以剪法共 $(i-1)+(j-1)$ 种；沿第 $a$ 条横线剪得到 $a \times j$ 与 $(i-a) \times j$ 两张纸，后继局面的 SG 值为二者异或 $\operatorname{SG}(a,j) \oplus \operatorname{SG}(i-a,j)$。于是

递推按面积从小到大进行（剪出来的纸一定更小），$N, M \leqslant 200$ 时状态 $O(N^2)$、转移 $O(N)$，总计 $O(N^3) \approx 8 \times 10^6$，轻松通过。

关键：处理"先剪出 1×1 者获胜"这条特殊规则

SG 定理的标准形式假设"无法行动者败"，而本题是"先剪出 $1\times 1$ 者胜"，需要做一个转化。

考虑 $1 \times k\ (k \geqslant 2)$ 的纸：面对它的人沿唯一的格线一剪，就得到 $1 \times 1$，立即获胜。所以我们把 $1 \times k$ 称为一枚炸弹——谁的局面里出现 $1 \times k$，轮到谁走谁就赢。

由此得到两个推论：

1. 任何剪出 $1 \times k$ 部分的剪法都是"送炸弹"：剪完后炸弹在对手面前，对手下一手直接获胜。这类剪法是自寻死路，理性的玩家绝不会主动选择——它们对"是否存在 SG 为 $0$ 的后继"没有任何贡献，计算 mex 时可以整体忽略。
2. 如果对手把炸弹送上门（即收到的局面里已有 $1 \times k$），我直接剪它获胜。在递推里这意味着：含 $1 \times k$ 部分的局面"面对者必胜"，其 SG 值为 $0$（它是某些剪法的必胜后继，等价于"安全剪法"集合中 SG 为 $0$ 的出边，不影响 mex 的 $0$ 值判定）。

于是只保留"安全剪法"——剪开后两部分长宽都 $\geqslant 2$ 的剪法——来计算 mex：

并约定 $\operatorname{SG}(i, 1) = \operatorname{SG}(1, j) = 0$（$1 \times k$ 是炸弹，面对它的人必胜，SG 记 $0$）。

另一个实现细节：剪在 $a$ 处与剪在 $i - a$ 处得到的两块互换，异或值相同，所以枚举 $a$ 只需到 $\lfloor i/2 \rfloor$，转移常数减半。

用样例验证模型

$\operatorname{SG}(2,2)$：唯一的剪法是 $1\times2 + 1\times2$，送出两枚炸弹，不属于安全剪法，mex 空集得 $0$ → LOSE。$\operatorname{SG}(3,2)$：横剪得 $1\times2+2\times2$（送炸弹），竖剪不存在（宽只有 2，无内部竖线），同样没有安全剪法，$0$ → LOSE。$\operatorname{SG}(4,2)$：剪成 $2\times2+2\times2$，$0 \oplus 0 = 0$ 出现在后继集合中，mex 至少为 $1$ → WIN。三个样例全部对上。

$\operatorname{SG}$ 值不为 $0$ 并不代表"这张纸不能剪"，而是"怎么剪都会把主动权交给对手"——这正是"无法行动者败"与"先剪出 $1\times1$ 者胜"两种规则之间微妙的差异所在。

一张 $2 \times 3$ 的纸从被剪到分出胜负的完整链条：

flowchart TD
    A["2×3 先手，SG=0 必败"] -->|"横剪：1×3 + 1×3"| B["两张 1×3 都是炸弹<br>对手任取一张一剪即得 1×1 获胜"]
    A -->|"竖剪：2×1 + 2×2"| C["2×1 是炸弹<br>对手一剪得 1×1 获胜"]

可以看到 $2 \times 3$ 的所有剪法（$i=2$ 的 $1$ 条横线、$j=3$ 的 $2$ 条竖线）都会产生一枚 $1 \times k$ 炸弹，安全剪法集合为空。先手无论怎么走都在送炸弹，故为必败态。反过来，$4 \times 2$ 先手一剪成 $2\times2+2\times2$，两张 $2 \times 2$ 都是 SG 为 $0$ 的"死纸"（谁先动谁送命），异或和为 $0$ 的局面轮到对手，先手稳赢。

SG 表长什么样

递推得到的部分 SG 表（行、列均为纸的长和宽，$2 \sim 12$）：

观察重点：

• 加粗的 $0$ 就是必败格：$2 \times 2$、$3 \times 2$（样例）以及 $2 \times 3$、$7 \times 2$、$11 \times 3$ 等，并非只有"剪不动"的纸才是必败态。
• 第 $4, 5, 9, 10$ 行整行都是 $1$：这些纸存在一类安全剪法把局面导回异或和 $0$，但没有后继的异或值恰好为 $1$，mex 卡在 $1$。
• 表中数值最大只到 $3$，后继 SG 异或值的分布非常集中，这也是"只保留安全剪法"后递推仍然闭合（不依赖被忽略剪法）的直观体现。
• 注意 SG 表没有简单的小周期（如第 $6$ 行与第 $2$ 行不同），不能试图找规律直接输出，老老实实递推即可。

整个求解流程：

flowchart LR
    A["读入全部 N M"] --> B["按面积从小到大递推<br>sg[i][j] = mex(安全剪法后继的异或值)"]
    B --> C["每组询问 O(1) 查表"]
    C -->|"sg ≠ 0"| D["WIN"]
    C -->|"sg = 0"| E["LOSE"]

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 16:46
# update_at: 2026-10-01 16:46

import sys

N = 200  # 题面数据范围：2 ≤ N, M ≤ 200


def mex(values: set[int]) -> int:
    """values 之外的最小非负整数，即 SG 值的定义。"""
    m = 0
    while m in values:
        m += 1
    return m


def build_sg(limit: int) -> list[list[int]]:
    """sg[i][j]：i×j 的纸（i,j≥2）只保留"安全剪法"时的 SG 值。"""
    sg = [[0] * (limit + 1) for _ in range(limit + 1)]
    for i in range(2, limit + 1):
        row_i = sg[i]
        for j in range(2, limit + 1):
            # 只枚举剪开后两部分长宽都 ≥2 的剪法：剪出 1×k 的剪法必送对手
            # 一个含 1×k 的必胜局面（对手把它剪出 1×1 直接获胜），可整体忽略。
            # 剪在 a 与剪在 i-a 得到的两块互换，异或值相同，枚举一半即可。
            options = {sg[a][j] ^ sg[i - a][j] for a in range(2, i // 2 + 1)} | {
                sg[i][b] ^ sg[i][j - b] for b in range(2, j // 2 + 1)
            }
            row_i[j] = mex(options)
    return sg


def solve() -> None:
    sg = build_sg(N)
    data = iter(map(int, sys.stdin.buffer.read().split()))
    print('\n'.join('WIN' if sg[n][m] else 'LOSE' for n, m in zip(data, data)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 22:20
 * update_at: 2026-10-04 22:20
 */
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

const int LIM = 200; // 题面数据范围 2 ≤ N,M ≤ 200

int sg[LIM + 1][LIM + 1]; // sg[i][j]：i×j 的纸只保留安全剪法时的 SG 值
bool used[LIM * 2 + 5];   // mex 临时标记数组，范围够放所有异或值

// 按面积从小到大递推 SG 表；只保留剪开后两边长宽都 ≥2 的安全剪法
void build_sg() {
    for (int i = 2; i <= LIM; ++i) {
        for (int j = 2; j <= LIM; ++j) {
            // 枚举横向安全剪法：上、下两块高度都 ≥2
            for (int a = 2; a <= i - a; ++a) {
                used[sg[a][j] ^ sg[i - a][j]] = true;
            }
            // 枚举纵向安全剪法：左、右两块宽度都 ≥2
            for (int b = 2; b <= j - b; ++b) {
                used[sg[i][b] ^ sg[i][j - b]] = true;
            }
            // mex：不在 used 中的最小非负整数
            int g = 0;
            while (used[g]) ++g;
            sg[i][j] = g;
            // 清理本次用过的标记，只清实际用到的范围
            for (int a = 2; a <= i - a; ++a) used[sg[a][j] ^ sg[i - a][j]] = false;
            for (int b = 2; b <= j - b; ++b) used[sg[i][b] ^ sg[i][j - b]] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build_sg();

    ll n, m;
    while (cin >> n >> m) {
        cout << (sg[n][m] ? "WIN" : "LOSE") << '\n';
    }
    return 0;
}

复杂度

• 时间复杂度：$O(N^3)$ 建表（$N, M \leqslant 200$ 时约 $8 \times 10^6$ 次状态转移计算），每组询问 $O(1)$ 查表。
• 空间复杂度：$O(N^2)$ 的 SG 表。

总结

• 把"每步只动一张纸"识别为独立子游戏的和，用 SG 定理把多纸局面压成异或和，初始只有一张纸，问题就是求 $\operatorname{SG}(N,M)$ 是否为 $0$。
• "先剪出 $1\times1$ 者胜"通过**炸弹（$1 \times k$）**分析转化为标准 SG 规则：送炸弹的剪法必败，计算 mex 时只保留两部分长宽都 $\geqslant 2$ 的安全剪法。
• 剪切位置 $a$ 与 $i-a$ 对称，枚举到一半即可；递推按面积从小到大，$O(N^3)$ 建表后 $O(1)$ 回答询问。
• 易错点：SG 为 $0$ 不等于"不能剪"；不要把"剪出 $1\times1$ 直接获胜"的剪法当成普通后继参与 mex。

图示解析

一个必败局面的完整对局

以样例 $3 \times 2$（即旋转后的 $2 \times 3$）为例，把"先手无论怎么走都会输"走到底：

若后手不急着剪炸弹而去剪 2×2，只会把炸弹再留给对手处理；对手剪掉炸弹后局面回到"一张 $2 \times 2$ 且轮到后手"，后手依然必败。每条分支的终点都是对手剪出 $1 \times 1$，这正是 $\operatorname{SG}(3,2)=0$ 的博弈含义。