9463 - Nim博弈(nim)

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 2 秒

内存限制 : 512 MB

Alice和Bob又在玩取石子游戏了。这一回的规则如下：

游戏双方轮流从若干个石堆中取石子，每个石堆的数量不一定相同。每人每次只能选取一堆，从中取石子，并且从中取走至少1颗，数量任选（当然也不可能超过石堆中剩余石子个数）。

如果某人无石子可取，则算负。

假如Alice和Bob总是聪明绝顶，总会使用最优的策略。求先手玩家Alice是否必胜？

上述博弈模型是经典的Nim博弈。Nim博弈的法则是：当对剩余所有石子求异或和的结果是0时，当前玩家必败，反之则必胜。

输入

输入的第一行包含二个正整数 n和m，分别表示输入的数列长度和操作的数量。

第二行包含 $n$ 个正整数，第 $i$ 项表示数列第 $i$ 个元素的值 $a_i$ 。

接下来 $m$ 行，每行为一条操作，格式为下列三种之一：

操作1： xor x y k，表示把数列的第x项到第y项每一项异或 $(\oplus)k$ 。

操作2： set x k，表示把数列的第x项的值改为 $k$ 。

操作3： game x y，表示把数列的第 $x$ 项到第 $y$ 项当作游戏开始时的所有石堆，求出先手玩家Alice是否必胜和Alice第一步可以选择取走石子的石堆数。

输出

输出若干行，即每次操作3的结果，当Alice先手玩家必胜时，输出true，空一格后输出第一步可以选择取走石子的石堆数。

当Alice必败时，输出false即可。

样例

输入

9 12
2 9 12 11 2 1 3 15 13 
game 5 7
xor 1 4 3
game 6 9
game 3 4
set 2 6
xor 2 8 1
set 1 4
xor 9 9 11
xor 5 6 1
game 4 5
set 4 15
game 2 7

输出

false
false
true 1
true 1
true 3

输入

9 24
15 2 10 8 10 11 3 13 6 
game 2 4
xor 2 5 12
game 1 8
xor 1 7 10
game 1 2
game 7 8
xor 1 9 4
xor 1 6 7
game 5 7
game 4 6
game 3 8
set 7 6
set 1 13
set 4 2
game 2 6
xor 2 7 15
game 2 9
game 3 3
xor 1 7 12
set 7 5
xor 1 6 7
xor 1 1 1
xor 2 9 7
game 3 6

输出

false
false
true 1
true 1
false
false
true 5
true 3
true 5
false
false

提示

【样例1解释】

初始数列为{2,9,12,11,2,1,3,15,13}。

第1步操作:选择第5个数到第7个数作为初始石堆开始游戏，即2 1 3，2⨁1⨁3=0,Alice先手必败。第2步操作:选择第1个数到第4个数和3做异或运算。

$a_1⨁$ 3=1， $a_2⨁$ 3=10， $a_3⨁$ 3=15， $a_4⨁$ 3=8。数列变成了{1,10,15,8,2,1,3,15,13}。

第3步操作:选择第6个数到第9个数作为初始石堆开始游戏，即1 3 15 13，3⨁15⨁13=0,Alice先手必败。

第4步操作:选择第3个数到第4个数作为初始石堆开始游戏，即15 8，15⨁8=7,Alice必胜，Alice只能在第一步选择15石堆取走其中7个,这样不论Bob怎么操作，都可以使得两个石堆的剩余数量相同。

第5步操作:把第2个数的值改为6。数列变成了{1,6,15,8,2,1,3,15,13}。

第6步操作:选择第2个数到第8个数和1做异或运算。数列变成了{1,7, 14,9,3,0,2,14,13}。

第7步操作:把第1个数的值改为4。数列变成了{4,7,14,9,3,0,2,14,13}。

第8步操作:选择第9个数和11做异或运算。数列变成了{4,7,14,9, 3,0,2,14,6}。

第9步操作:选择第5个数到第6个数和1做异或运算。数列变成了{4, 7, 14, 9, 2, 1, 2, 14, 6}。

第10步操作:选择第4个数到第5个数作为初始石堆开始游戏，即9 2，9⨁2=11,Alice必胜，Alice只能在第一步选择9石堆取走其中7个。

第11步操作: 把第4个数的值改为15。数列变成了{4, 7, 14, 15, 2, 1, 2, 14, 6}。

第12步操作:选择第2个数到第7个数作为初始石堆开始游戏，7⨁14⨁15⨁2⨁1⨁2=7,Alice必胜，Alice可以选择数量为7 14 15的三个石堆作为第一次操作的石堆。

【数据范围】

对于所有测试数据有： $1\leqn,m\leq 2\times10^5,1\leqx\leqy\leqn,0\leqa_i,k\leq2024$

特殊性质A：对于所有操作1和操作3，满足x_i=y_i。

特殊性质B：对于所有操作1和操作3，满足 $y_i-x_i\leq1000$ 。

特殊性质C：对于所有 $a_i,k\leq1$ 。

特殊性质D：不存在操作1。

来源

云南编程挑战赛