QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 4106. 硬币游戏

统计

Alice 和 Bob 现在在玩的游戏,主角是依次编号为 $1$ 到 $n$ 的 $n$ 枚硬币。每一枚硬币都有两面,我们分别称之为正面和反面。一开始的时候,有些硬币是正面向上的,有些是反面朝上的。Alice 和 Bob 将轮流对这些硬币进行翻转操作,且Alice 总是先手。

具体来说每次玩家可以选择一枚编号为 $x$,要求这枚硬币此刻是反面朝上的。对于编号 $x$ 来说,我们总可以将 $x$ 写成 $x=c \cdot 2^a \cdot 3^b$,其中 $a$ 和 $b$ 是非负整数,$c$ 是与 $2, 3$ 都互质的非负整数,然后有两种选择:

  1. 选择整数 $p, q$ 满足 $a \geq pq, \ p \geq 1$ 且 $1 \leq q \leq \text{MAXQ}$,然后同时翻转所有编号为 $c \cdot 2^{a-pj} \cdot 3^b$ 的硬币,其中 $j = 0, 1, 2, \ldots , q$。
  2. 选择整数 $p, q$ 满足 $b \geq pq, \ p \geq 1$ 且 $ 1 \leq q \leq \text{MAXQ}$,然后同时翻转所有编号为 $c \cdot 2^a \cdot 3^{b-pj}$ 的硬币,其中 $j = 0, 1, 2, \ldots , q$。

可以发现这个游戏不能无限进行下去,当某位玩家无法继续操作上述操作时,便输掉了游戏。作为先手的 Alice,总是希望可以在比赛开始之前就知道自己能否获胜。她知道自己和 Bob 都是充分聪明的,所以在游戏过程中,两人都会最优化自己的策略并尽量保证自己处于不败的情形中。

输入格式

本题有多组测试数据,第一行输入一个整数 $T$,表示总的数据组数。

之后给出 $T$ 组数据,每组数据第一行输入两个整数 $n, \text{MAXQ}$;

第二行输入 $n$ 个整数,第 $i$ 个数表示第 $i$ 个硬币的初始状态,0 表示反面朝上,1 表示正面朝上。

输出格式

输出共有 $T$ 行。对于每一组数据来说,如果 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

子任务

测试点 $n \leq $ $\text{MAXQ} \leq $
$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 \leq n \leq 30\,000, \ 1 \leq \text{MAXQ} \leq 20, \ t \leq 100$。