题目
数论章节中的最后一题,也是博弈论的最后一节。
堆ai拆分成b1,b2后,一个重要的性质就是sg(b1,b2) = sg(b1) ^ sg(b2)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
static int N = 110;
static int f[] = new int[N];
public static void main(String[] args) throws IOException {
String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
Arrays.fill(f, -1);
int res = 0;
s = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
int x = Integer.parseInt(s[i]);
res ^= sg(x);
}
if (res == 0) pw.println("No");
else pw.println("Yes");
pw.flush();
pw.close();
br.close();
}
public static int sg(int x) {
if (f[x] != -1) return f[x];
Set<Integer> set = new HashSet<>();
for (int i = 0; i < x; i++)
for (int j = 0; j < i; j++)
set.add(sg(i) ^ sg(j));
//mex
for (int i = 0; ; i++)
if (!set.contains(i))
return f[x] = i;
}
}