首先了解一个结论吧。

局面的SG值为局面中每个正(反)面朝上的棋子单一存在时的SG值的异或和

这里有证明,糊不糊不知道,内附比较严谨的证明。


回到正题。

对于$c*2^a*3^b$,$c$其实没什么用,因为$c$不同,其实之间是互相独立的游戏,用一下SG定理就可以求得游戏和了。

那么就考虑独立的$2^a*3^b$,根据题意,$2^a$与$3^b$的局面的并集其实就是$2^a*3^b$的局面。

因此仅需要考虑$2^a$的情况。

由于改动的只有$2^a,2^{a-pj}(j\le q,p*q\le a)$

不妨指数拿下来,也就是改变$a,a-p,a-2p,\cdots,a-pq$这些位置的硬币朝向。

也就是根据上面的结论局面SG值等于单一存在时的SG的异或和,$SG(a)$的状态来源有$SG(a-p),SG(a-p)~\text{xor}~SG(a-2p),\cdots$

于是$SG(a)=\text{mex}\{SG(a-p),SG(a-p)~\text{xor}~SG(a-2p),\cdots\}$

然后回归原题,也就是

$SG(a,b)=\text{mex}\{SG(a-p,b),SG(a-p,b)~\text{xor}~SG(a-2p,b),\cdots,SG(a,b-p),SG(a,b-p)~\text{xor}~SG(a,b-2p),\cdots\}$

最后再异或一下就是答案了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=3e4,M=N+5;const ull G=31;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int sg[21][30][30],lg2[M],lg3[M];
I int mex(int k){for(int i=0;;i++)if(~k>>i&1)return i;}
int main()
{
    for(int i=1;i<=N;i++)
    {
        if(i%2==0)lg2[i]=lg2[i/2]+1;
        if(i%3==0)lg3[i]=lg3[i/3]+1;
    }
    for(int MaxQ=1;MaxQ<=20;MaxQ++)
        for(int a=1,j=0;a<=N;a*=2,++j)
            for(int b=1,k=0;a*b<=N;b*=3,++k)
            {
                int s=0;
                for(int p=1;p<=j;p++)
                {
                    int t=0;
                    for(int q=1;p*q<=j&&q<=MaxQ;q++)
                        t^=sg[MaxQ][j-p*q][k],s|=1<<t;
                }
                for(int p=1;p<=k;p++)
                {
                    int t=0;
                    for(int q=1;p*q<=k&&q<=MaxQ;q++)
                        t^=sg[MaxQ][j][k-p*q],s|=1<<t;
                }
                sg[MaxQ][j][k]=mex(s);
            }
    int T;qr(T);
    while(T--)
    {
        int ans=0;
        int n,MaxQ;qr(n),qr(MaxQ);
        for(int i=1;i<=n;i++)
        {
            int c;qr(c);
            if(!c)ans^=sg[MaxQ][lg2[i]][lg3[i]];
        }
        ans?puts("win"):puts("lose");
    }
    return 0; 
}