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.

样例输入

14
25 11 30
35 19 19
423 15 6
52 26 16
63
79 20 9
88 1 28
930 22 26

样例输出

1Yes
2No

提示

无

思路

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

代码

 1using namespace std;
 2
 3/*
 4    Nim积 x @ y = mex{(a @ y) ^ (x @ b) ^ (a @ b)}, 0 <= a < x, 0 <= b < y
 5
 6    1. X x 2^(2^a) = X * 2^(2^a)
 7    2. X x Y < 2^(2^a)
 8    3. 2^(2^a) x 2^(2^a) = (3/2) * 2^(2^a)
 9
10    调用 ans ^= f(x, y)
11*/
12
13
14int SG[20][20];
15
16int f(int, int);
17int g(int x, int y)                         // 计算2^x与2^y的nim积
18{
19    if(SG[x][y] != -1) return SG[x][y];
20    if(!x) return SG[x][y] = 1<<y;          // x==0也就是1与2^y的nim积，等于2^y
21    if(!y) return SG[x][y] = 1<<x;
22
23    int ans=1, t;
24    int xx=x, yy=y, k=1;
25    while(x || y)                           // 再将x和y分为二进制，这里计算那些普通乘积的（即对应二进制位不同的）
26    {
27        t = 1<<k;                           // 从此位得到的最终的数2^k
28        if((x^y)&1)  ans *= t;              // 该位不同
29        x>>=1; y>>=1; k<<=1;                // 从此位得到的指数(本身也是2的幂)
30    }
31
32    x=xx; y=yy; k=1;
33    while(x || y)                           // 计算那些相同的fermat 2-power 数，与已得出的数的nim积
34    {
35        t = 1<<k;
36        if ((x&y)&1) ans = f(ans, t/2*3);   // 该位相同
37        x>>=1; y>>=1; k<<=1;                // 从此位得到的指数(本身也是2的幂)
38    }
39    return SG[xx][yy] = ans;
40}
41
42int f(int x, int y)                         //计算二位Nim积
43{
44    if(!x || !y) return 0;
45    if(x == 1) return y;
46    if(y == 1) return x;
47
48    int ans=0;
49    for (int i=x, a=0; i; i>>=1, a++)       //将x和二进制分解
50    {
51        if ((i&1)==0) continue;             //该位是1才计算
52        for (int j=y, b=0; j; j>>=1, b++)
53        {
54            if ((j&1)==0) continue;
55            ans ^= g(a, b);
56        }
57    }
58    return ans;
59}
60
61int main()
62{
63    memset(SG, -1, sizeof(SG));
64    int n;
65    while(~scanf("%d", &n) && n)
66    {
67        int nim=0;
68        for(int i=0; i<n; i++){
69            int x, y, z;
70            scanf("%d %d %d", &x, &y, &z);
71            nim ^= f(x, f(y, z));
72        }
73        if(nim){
74            printf("No\n");
75        }else{
76            printf("Yes\n");
77        }
78    }
79    return 0;
80}