#PQJ223x4106. QOJ 223_4106
QOJ 223_4106
Alice 和 Bob 现在在玩的游戏,主角是依次编号为 1 到 𝑛 的 𝑛 枚硬币。每一枚硬币都有两面,我们分别称之为正面和反面。一开始的时候,有些硬币是正面向上的,有些是反面朝上的。Alice 和 Bob 将轮流对这些硬币进行翻转操作,且Alice 总是先手。
具体来说每次玩家可以选择一枚编号为 𝑥 ,要求这枚硬币此刻是反面朝上的。对于编号 𝑥 来说,我们总可以将 𝑥 写成 𝑥
𝑐 ⋅ 2 𝑎 ⋅ 3 𝑏 ,其中 𝑎 和 𝑏 是非负整数, 𝑐 是与 2 , 3 都互质的非负整数,然后有两种选择:
选择整数 𝑝 , 𝑞 满足 𝑎 ≥ 𝑝 𝑞 , 𝑝 ≥ 1 且 1 ≤ 𝑞 ≤ MAXQ ,然后同时翻转所有编号为 𝑐 ⋅ 2 𝑎 − 𝑝 𝑗 ⋅ 3 𝑏 的硬币,其中 𝑗
0 , 1 , 2 , … , 𝑞 。 选择整数 𝑝 , 𝑞 满足 𝑏 ≥ 𝑝 𝑞 , 𝑝 ≥ 1 且 1 ≤ 𝑞 ≤ MAXQ ,然后同时翻转所有编号为 𝑐 ⋅ 2 𝑎 ⋅ 3 𝑏 − 𝑝 𝑗 的硬币,其中 𝑗
0 , 1 , 2 , … , 𝑞 。
可以发现这个游戏不能无限进行下去,当某位玩家无法继续操作上述操作时,便输掉了游戏。作为先手的 Alice,总是希望可以在比赛开始之前就知道自己能否获胜。她知道自己和 Bob 都是充分聪明的,所以在游戏过程中,两人都会最优化自己的策略并尽量保证自己处于不败的情形中。
输入格式
本题有多组测试数据,第一行输入一个整数 𝑇 ,表示总的数据组数。
之后给出 𝑇 组数据,每组数据第一行输入两个整数 𝑛 , MAXQ ;
第二行输入 𝑛 个整数,第 𝑖 个数表示第 𝑖 个硬币的初始状态,0 表示反面朝上,1 表示正面朝上。
输出格式
输出共有 𝑇 行。对于每一组数据来说,如果 Alice 先手必胜,则输出 "win",否则输出 "lose"(均不包括引号)。
样例数据 样例输入 6 16 14 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 16 14 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 16 11 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 16 12 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 16 4 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 16 20 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 样例输出 win lose win lose win win 子任务 测试点 𝑛 ≤
MAXQ ≤
1
16
20
2
32
20
3
36
20
4
40
20
5
10 000
1
6
20 000
1
7
30 000
1
8
10 000
20
9
20 000
20
10
30 000
20
对于 100 % 的数据, 1 ≤ 𝑛 ≤ 30 000 , 1 ≤ MAXQ ≤ 20 , 𝑡 ≤ 100 。