AcWing 893. 集合-Nim游戏
原题链接
简单
作者:
皓首不倦
,
2020-09-05 12:36:35
,
所有人可见
,
阅读 306
'''
DAG游戏SG函数应用,将每一堆石子看做一个有向图的起点,计算每一个起点的SG
再求所有起点的SG的异或值即可
'''
n = int(input())
edge_w = list(map(int, input().split()))
m = int(input())
start_val = list(map(int, input().split()))
# 计算SG函数数值
from functools import lru_cache
@lru_cache(typed=False, maxsize=128000000)
def sg(val) -> int:
if val == 0:
return 0
sg_vals = set()
for w in edge_w:
if val >= w:
sg_vals.add(sg(val - w))
ans = 0
while ans in sg_vals:
ans += 1
return ans
xor_val = 0
for start_v in start_val:
xor_val ^= sg(start_v)
print('Yes' if xor_val != 0 else 'No')