bzoj 4600 硬币游戏

Posted on | Views:

博弈论.

  • 操作一枚硬币,它只能影响到 $c$ 与自己相同的硬币.于是 $SG$ 函数就只需要 $a,b$ 两个状态.
  • 而 $a,b$ 是指数,非常小,所以状态数目也很少,直接暴力计算 $SG$ 函数即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=25;
int SG[MAXN][MAXN][MAXN];
void init_SG(int maxq)
{
	vector<int> s;
	int tmp=0;
	for(int a=0;a<=20;++a)
		for(int b=0;b<=20;++b)
		{
			s.clear();
			for(int p=1;p<=20;++p,tmp=0)
				for(int q=1;q<=maxq && p*q<=a;++q)
				{
					tmp^=SG[maxq][a-p*q][b];
					s.push_back(tmp);
				}
			for(int p=1;p<=20;++p,tmp=0)
				for(int q=1;q<=maxq && p*q<=b;++q)
				{
					tmp^=SG[maxq][a][b-p*q];
					s.push_back(tmp);
				}
			sort(s.begin(),s.end());
			int siz=s.size();
			if(!siz || s[0])
			{
				SG[maxq][a][b]=0;
				continue;
			} 
			for(int i=1;i<siz;++i)
			{
				if(s[i]-s[i-1]>=2)
				{
					SG[maxq][a][b]=s[i-1]+1;
					break;
				}
			}
			if(!SG[maxq][a][b])
				SG[maxq][a][b]=s[siz-1]+1;
		}
}
int n,maxq;
int main()
{
	for(int i=1;i<=20;++i)
		init_SG(i);
	int T=read();
	while(T--)
	{
		n=read(),maxq=read();
		int ans=0;
		for(int i=1;i<=n;++i)
		{
			int dir=read();
			if(dir)
				continue;
			int x=i,a=0,b=0;
			while(x%2==0)
				++a,x/=2;
			while(x%3==0)
				++b,x/=3;
			ans^=SG[maxq][a][b];
		}
		if(ans)
			puts("win");
		else
			puts("lose");
	}
	return 0;
}