$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$
题目描述
Urej 喜欢玩各种类型的沉闷游戏。他通常会邀请其他人和他一起玩。他说，玩这些游戏可以展现他的非凡智慧。最近，Urej 对一个新游戏产生了极大兴趣，而 Erif Nezorf 成为了牺牲品。为了摆脱玩这样一个沉闷游戏的痛苦，Erif Nezorf 请求你的帮助。这个游戏使用一个由 $W \times H$ 格网组成的矩形纸张。两名玩家轮流将纸张切割成两个矩形部分。在每个回合中，玩家可以横向或纵向切割，保持每个格网完整。经过 $N$ 轮后，纸张将被切割成 $N+1$ 片，然后在后续的回合中，玩家可以选择任意一片进行切割。如果一名玩家切割出一个只有一个格网的纸片，他就赢得了游戏。如果这两个人都非常清楚，你应该写一个问题来告诉是否先手的玩家能赢得游戏。
输入格式
输入包含多个测试用例。每个测试用例在一行中只包含两个整数 $W$ 和 $H (2 \le W , H \le 200)$，分别表示原始纸张的宽度和高度。
输出格式
对于每个测试用例，应该只输出一行。如果先手的玩家能赢得游戏，则输出 "WIN"，否则输出 "LOSE"。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
题解
本题中，切割一张纸会得到两张更小的纸，实际上形成了两个独立的子游戏。
显然，$(1,x)$ 和 $(x,1)$ 都是必胜局面，因此双方选手都会尽可能避免剪出长或宽为 1 的矩形。
因此，$(2,2), (2,3), (3,2)$ 是最终的必败局面。
在决策树当中，我们把整张纸看做根节点，成对拆分的子图之间不是独立的。我们把两子图的 $\SG(G_1) \xor \SG(G_2)$ 作为对应决策的 $\SG$ 函数。 $$ \SG(n,m) = \mex(\set{\SG(i,m) \xor \SG(n-i,m), 2 \le i \le n-2} \ \cup \set{\SG(n,i) \xor \SG(n,m-i), 2 \le i \le m-2}) $$
开始局面先手必胜，当且仅当 $\SG(n,m) > 0$。
