P10501 Cutting Game

$$$$

原题链接：P10501 Cutting Game - 洛谷

题目描述

Urej 喜欢玩各种类型的沉闷游戏。他通常会邀请其他人和他一起玩。他说，玩这些游戏可以展现他的非凡智慧。最近，Urej 对一个新游戏产生了极大兴趣，而 Erif Nezorf 成为了牺牲品。为了摆脱玩这样一个沉闷游戏的痛苦，Erif Nezorf 请求你的帮助。这个游戏使用一个由 $W\times H$ 格网组成的矩形纸张。两名玩家轮流将纸张切割成两个矩形部分。在每个回合中，玩家可以横向或纵向切割，保持每个格网完整。经过 $N$ 轮后，纸张将被切割成 $N+1$ 片，然后在后续的回合中，玩家可以选择任意一片进行切割。如果一名玩家切割出一个只有一个格网的纸片，他就赢得了游戏。如果这两个人都非常清楚，你应该写一个问题来告诉是否先手的玩家能赢得游戏。

输入格式

输入包含多个测试用例。每个测试用例在一行中只包含两个整数 $W$ 和 $H(2\le W,H\le 200)$，分别表示原始纸张的宽度和高度。

输出格式

对于每个测试用例，应该只输出一行。如果先手的玩家能赢得游戏，则输出 "WIN"，否则输出 "LOSE"。

翻译来自于：ChatGPT

输入输出样例 #1

输入 #1

2 2
3 2
4 2

输出 #1

LOSE
LOSE
WIN

题解

本题中，切割一张纸会得到两张更小的纸，实际上形成了两个独立的子游戏。

显然，$(1,x)$ 和 $(x,1)$ 都是必胜局面，因此双方选手都会尽可能避免剪出长或宽为 1 的矩形。

因此，$(2,2),(2,3),(3,2)$ 是最终的必败局面。

在决策树当中，我们把整张纸看做根节点，成对拆分的子图之间不是独立的。我们把两子图的 $\mathrm{SG}(G_1)\text{ xor }\mathrm{SG}(G_2)$ 作为对应决策的 $\mathrm{SG}$ 函数。

$$\begin{gathered} \mathrm{SG}(n,m)=\mathrm{mex}(\{\mathrm{SG}(i,m)\text{ xor }\mathrm{SG}(n-i,m),2\le i\le n-2\}\text{ \\ ∪{SG(n,i) xor SG(n,m−i),2≤i≤m−2})} \end{gathered}$$

开始局面先手必胜，当且仅当 $\mathrm{SG}(n,m)>0$。