先考虑$x=y$​的情况，此时即是一个平等博弈，因此考虑$sg$​​函数

具体的，有$sg(n)=\begin{cases}0&(n=0)\\mex(\{sg(n-i)\mid 1\le i\le n,i\ne x\})&(n\ge 1)\end{cases}$​​​，简单计算$sg(n)$​的前几项，不难发现规律$sg(n)=\lfloor\frac{n}{2x}\rfloor x+n\ mod\ x$​​，进而将其异或即可

（若异或和为0则先手必败，否则先手必胜）

接下来，不妨假设$x>y$​且$a_{1}\le a_{2}\le ...\le a_{n}$​，此时再分类讨论：

1.若$a_{n}<y$​​​，显然限制没有意义，仍是一个平等博弈，并且有$sg(n)=n$​​​​​​

2.若$a_{n}\ge y$​​​​​​，此时先手必胜，分类讨论证明如下——

(1)若$a_{n-1}<y$（或$n=1$​），此时先手只需要保证操作后后手不能使$a_{n}<y$即可（如果这样异或和一定非0），显然总会有$a_{n}<y$，那么即先手必胜，再对$\bigoplus_{i=1}^{n}a_{i}$​分类讨论：

a.若$\bigoplus_{i=1}^{n}a_{i}\ne 0$，总存在$(i,z)$使得在第$i$堆取$z$​个后$\bigoplus_{i=1}^{n}a_{i}=0$（其中$1\le z\le a_{i}$​）

若$z\ne x$，直接操作即可；若$z=x$，显然$i=n$，那么改为取$x-y$个（仍在第$n$堆中）即可

b.若$\bigoplus_{i=1}^{n}a_{i}=0$​​​，假设在第$n$​​堆中取$y$​​​个，显然此时后手可以操作使得异或和为0，那么先执行后手所要执行（指在第$n$​​堆取$y$​​个后）的操作即可

(2)若$a_{n-1}\ge y$，显然初始有两个$\ge y$的堆，而若仅有两个$\ge y$的堆（允许还有$<y$的堆），此时后手显然不能使$\ge y$的堆变为$<y$的堆，因此先手最终不难使得状态为$a_{1}=a_{2}=...=a_{n-2}=0$且$a_{n-1}=a_{n}=y$，对此时的先后手分类讨论：

a.若先手"先手"，那么将一堆取光，显然后手不能取光，那么下一步再取光另一堆即可

b.若先手"后手"，那么模仿后手操作即可

综上，即得证

类似地，对于$x<y$​的情况，再分类讨论：

1.若$a_{n}<x$​​，与之前（指$x>y$​时）的第1种情况相同

2.若$a_{n}\ge x$，此时先手操作后如果仍有$\max_{i=1}^{n}a_{i}\ge x$，那么与之前的证明相同，后手必胜

换言之，先手必胜的必要条件为$a_{n-1}<x$（或$n=1$）且存在一种方式操作$a_{n}$后$a_{n}<x$且异或和为0，显然后者也即要求$S<x$且$S\ne a_{n}-x$（其中$S=\bigoplus_{i=1}^{n-1}a_{i}$）

（同时，显然这也是充分条件）

综上，时间复杂度为$o(n\log n)$​​​（排序），可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1005
 4 int t,n,x,y,ans,a[N];
 5 int main(){
 6     scanf("%d",&t);
 7     while (t--){
 8         scanf("%d%d%d",&n,&x,&y);
 9         for(int i=1;i<=n;i++)scanf("%d",&a[i]);
10         ans=0;
11         if (x==y){
12             for(int i=1;i<=n;i++)ans^=a[i]/(x<<1)*x+a[i]%x;
13             if (ans)printf("Jslj\n");
14             else printf("yygqPenguin\n");
15             continue;
16         }
17         sort(a+1,a+n+1);
18         if (a[n]<min(x,y)){
19             for(int i=1;i<=n;i++)ans^=a[i];
20             if (ans)printf("Jslj\n");
21             else printf("yygqPenguin\n");
22             continue;
23         }
24         if (x>y)printf("Jslj\n");
25         else{
26             if ((n==1)||(a[n-1]<x)){
27                 for(int i=1;i<n;i++)ans^=a[i];
28                 if ((ans<x)&&(ans!=a[n]-x))printf("Jslj\n");
29                 else printf("yygqPenguin\n");
30             }
31             else printf("yygqPenguin\n");
32         }
33     }
34     return 0;
35 } 

View Code