有n个关闭的箱子, 每个箱子里ai块石头, 两人轮流操作, 每次二选一: - 开启任意 (大于0) 个关闭的箱子 - 从某个开启了的箱子里取出任意 (大于0) 块石头
两人均采取最优策略, 问先手是否必胜. T组数据. (T≤10, n≤20, ai≤10^9) bzoj上此题无法提交. 由于在高斯消元的分类下找到这个问题......推测先手是否必胜和是否存在异或和等于0的非空子集有关.
事实的确如此.
考虑局面A: 开启的箱子内石头数的异或和等于0, 且不存在这些箱子的一个真母集, 使得石头数异或和等于0. 这是一种先手必败状态. 对所有状态拓扑排序, 做数学归纳. - 如果所有箱子都开了, 则根据Nim游戏的结论, 先手必败. - 如果还剩m (m>0) 个箱子没开, 无论先手是开箱子还是拿石头, 已开启的箱子的石头数的异或和均非0, 后手总是可以通过拿石头使先手返回这样一种局面, 根据归纳假设, 先手必败.
接着, 容易证明局面B是先手必胜状态: 开启的箱子内石头数的异或和非0, 且不存在这些箱子的一个母集, 使得石头数异或和等于0. 先手可以通过拿石头使后手进入局面A.
如果存在异或和等于0的非空子集, 则先手开启其中最大的一个子集中的箱子, 后手进入局面A. 如果不存在, 由于先手只能选择开箱子, 所以后手进入局面B. 于是, 先手必胜当且仅当石头数存在异或和等于0的非空子集, 这可以通过高斯消元判断.