AcWing 894. 拆分-Nim游戏
原题链接
简单
作者:
皓首不倦
,
2020-09-05 18:05:10
,
所有人可见
,
阅读 381
'''
SG函数应用,每一堆石子的变化看成一个独立游戏
所有求所有独立游戏的SG的异或数值
'''
from functools import lru_cache
@lru_cache(typed=False, maxsize=128000000)
def sg(val) -> int:
if val == 0:
return 0
sg_vals = set()
# 一堆石子后面用不同的组合形式变成两堆石子,也就是两个独立游戏
# 原来一堆石子的下一个状态的SG就是两个子状态的SG的异或值
for i in range(0, val):
for j in range(i, val):
sg_vals.add(sg(i) ^ sg(j))
# 求当期那这堆石子的SG
ans = 0
while ans in sg_vals:
ans += 1
return ans
n = int(input())
arr = list(map(int, input().split()))
xor_val = 0
for val in arr:
xor_val ^= sg(val)
print('Yes' if xor_val != 0 else 'No')