【题解】POJ-3533 Light Switching Game

Light Switching Game(POJ-3533)

题面

The Light Switching Game is played on a 1000 × 1000 × 1000 cube of cells with a light in each cell, as Figure.1 shows. Initially, most of the lights are off while exactly N lights are on. Two players take moves alternately. A move consists of switching the lights at the corners of a cuboid, i.e. (x1,y1,z1), (x1,y1,z2), (x1,y2,z1), (x1,y2,z2), (x2,y1,z1), (x2,y1,z2), (x2,y2,z1), (x2,y2,z2) where 1 ≤ x1 ≤ x2 ≤ 1000, 1 ≤y1 ≤ y2 ≤ 1000, 1 ≤z1 ≤ z2 ≤ 1000 and the light at the corner (x2,y2,z2) must be on (and turned off after the move). Notice the cuboid is possibly degenerated to a rectangle, a line or even a single cell so that the player may also switching four, two or one besides eight lights in a move. The player loses the game when he can not take a move.

Figure.1

You will find out whether the second player can win if both players play optimally.

输入

There are multiple test cases.
Every test case starts with one line containing a single number N indicating the number of lights which is initially on. (N ≤ 100)
Each of the next N lines contains the coordinates (x, y, z) (1 ≤ x, y, z ≤ 1000) showing that the light at this position is on initially.

输出

One line for each test case which contains “Yes” or “No” indicating whether the second player can win the game.

样例输入

1
2
3
4
5
6
7
8
9
4
5 11 30
5 19 19
23 15 6
2 26 16
3
9 20 9
8 1 28
30 22 26

样例输出

1
2
Yes
No

提示

思路

Nim积,见【题解】HDU-3404 Switch lights

代码

查看代码
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
using namespace std;

/*
Nim积 x @ y = mex{(a @ y) ^ (x @ b) ^ (a @ b)}, 0 <= a < x, 0 <= b < y

1. X x 2^(2^a) = X * 2^(2^a)
2. X x Y < 2^(2^a)
3. 2^(2^a) x 2^(2^a) = (3/2) * 2^(2^a)

调用 ans ^= f(x, y)
*/


int SG[20][20];

int f(int, int);
int g(int x, int y) // 计算2^x与2^y的nim积
{
if(SG[x][y] != -1) return SG[x][y];
if(!x) return SG[x][y] = 1<<y; // x==0也就是1与2^y的nim积,等于2^y
if(!y) return SG[x][y] = 1<<x;

int ans=1, t;
int xx=x, yy=y, k=1;
while(x || y) // 再将x和y分为二进制,这里计算那些普通乘积的(即对应二进制位不同的)
{
t = 1<<k; // 从此位得到的最终的数2^k
if((x^y)&1) ans *= t; // 该位不同
x>>=1; y>>=1; k<<=1; // 从此位得到的指数(本身也是2的幂)
}

x=xx; y=yy; k=1;
while(x || y) // 计算那些相同的fermat 2-power 数,与已得出的数的nim积
{
t = 1<<k;
if ((x&y)&1) ans = f(ans, t/2*3); // 该位相同
x>>=1; y>>=1; k<<=1; // 从此位得到的指数(本身也是2的幂)
}
return SG[xx][yy] = ans;
}

int f(int x, int y) //计算二位Nim积
{
if(!x || !y) return 0;
if(x == 1) return y;
if(y == 1) return x;

int ans=0;
for (int i=x, a=0; i; i>>=1, a++) //将x和二进制分解
{
if ((i&1)==0) continue; //该位是1才计算
for (int j=y, b=0; j; j>>=1, b++)
{
if ((j&1)==0) continue;
ans ^= g(a, b);
}
}
return ans;
}

int main()
{
memset(SG, -1, sizeof(SG));
int n;
while(~scanf("%d", &n) && n)
{
int nim=0;
for(int i=0; i<n; i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
nim ^= f(x, f(y, z));
}
if(nim){
printf("No\n");
}else{
printf("Yes\n");
}
}
return 0;
}
_/_/_/_/_/ EOF _/_/_/_/_/