#PQJ223x4106. QOJ 223_4106

    ID: 2782 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2016动态规划

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 。