Switch lights(HDU-3404)

题面

lxhgww is playing a game with his computer Deep Blue. The game is played on a matrix containing lights. At first, some lights are on, while others are off. lxhgww and Deep Blue take turns to switch the lights. For each step, the player should choose a rectangle in the matrix: (x1 , y1) , (x1 , y2) , (x2 , y1) , (x2 , y2) , (x1<=x2,y1<=y2, the light at (x2, y2) should be on) and change the lights’ status on the four vertex of the rectangle, namely on to off, and off to on. The player turns all the lights off wins the game. Notice the rectangle is possibly degenerated to line or even a single cell so that the player may also switch two or one besides four lights in a move. Deep Blue’s strategy is perfect, if it has a chance to win, never will it lose. Does lxhgww have a chance to win if he takes the first step?

输入

The first line is an integer T(T<=100) indicating the case number. Each case has one integers n (n<= 1000 ), the number of on-lights at the beginning of the game. Then come n lines, each line has two integers, xi , yi, (1<=xi<=10000, 1<=yi<=10000) , so light at (xi, yi) is on at first. (No two lights at the same position)

输出

If lxhgww still has a chance to win, output “Have a try, lxhgww.”, otherwise tell lxhgww “Don’t waste your time.”

样例输入

12
22
31 2
42 1
52
61 1
72 2

样例输出

1Don't waste your time.
2Have a try, lxhgww.

提示

无

思路

一个二维矩阵上，有若干个亮着的灯泡 。 每次选择一个矩阵（右上角的灯泡必须是亮的），改变四个角灯泡的状态，不能操作的选手判负。

Nim积定义

$ x \otimes y = sg(x, y) = mex{(a \otimes y) \oplus (x \otimes b) \oplus (a \otimes b), 0 \le a \lt x, 0 \le b \lt y} $

以下是对于 x, y≤4 的一个小表。

0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 3 1 8
3 0 3 1 2 12
4 0 4 8 12 6

定义费马数Fermat 2-power为$ 2^{2^{k}} $，对于$ x,y < 2^{2^{k}} $有以下性质

  • 一个 Fermat 2-power 与任意小于它的数的 Nim 积为一般意义下乘法的积，即$ x \otimes 2^{2^{k}} = x * 2^{2^{k}} $

  • 一个 Fermat 2-power 与自己的 Nim 积为自己的 $ \frac{3}{2} $ 倍，即 $ 2^{2^{k}} \otimes 2^{2^{k}} = \frac{3}{2} * 2^{2^{k}}$

  • $ x \otimes y < 2^{2^{k}} $

根据性质可以得出递归求Nim积的板子。

详细参见论文《从“k倍动态减法游戏”出发探究一类组合游戏问题》。

代码

  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
 61/*
 62    k为最大的整数满足 M = 2^(2^k) <= x
 63 x = p * M + q, y = s * M + t
 64 x @ y = spMM + sqM + tpM + tq
 65    = M(sp+sq+tp) + tq + (M/2 @ sp)
 66
 67    模板二：调用 ans ^ Nim_Multi(x, y)
 68*/
 69
 70int getSg(int x, int y){
 71    if(!x || !y) return 0;
 72    if(SG[x][y]!=-1) return SG[x][y];
 73    bool S[1<<8] = {0};
 74
 75    for(int i=0; i<x; i++)
 76        S[getSg(i, y)] = 1;
 77
 78    for(int i=0; i<y; i++)
 79        S[getSg(x, i)] = 1;
 80
 81    for(int i=1; i<x; i++)
 82        for(int j=1; j<y; j++)
 83            S[getSg(i,y) ^ getSg(x,j) ^ getSg(i,j)] = 1;
 84
 85    int mex = 0;
 86    while(S[mex]) mex++;
 87    return SG[x][y]=mex;
 88}
 89
 90int Nim_Multi_Power(int x, int y)
 91{
 92    if (x < 16) return getSg(x, y);
 93    int a=1, m;
 94    for(; (1<<a) <= x; a<<=1);
 95    a >>= 1; m = 1<<a;
 96    int p = x/m, s = y/m, t = y&(m-1);
 97    int d1 = Nim_Multi_Power(p, s);
 98    int d2 = Nim_Multi_Power(p, t);
 99    return ((d1^d2) << a) ^ Nim_Multi_Power(m/2, d1);
100}
101
102int Nim_Multi(int x, int y)
103{
104    if (x < y) swap(x, y);
105    if (x < 16) return getSg(x, y);
106    int a=1, m;
107    for(; (1<<a) <= x; a<<=1);
108    a >>= 1; m = 1<<a;
109    int p = x/m, q = x&(m-1), s = y/ m, t = y&(m-1);
110    int c1 = Nim_Multi(p, s);
111    int c2 = Nim_Multi(p, t) ^ Nim_Multi(q, s);
112    int c3 = Nim_Multi(q, t);
113    return ((c1^c2) << a) ^ c3 ^ Nim_Multi_Power(m/2, c1);
114}
115
116
117int main()
118{
119    memset(SG, -1, sizeof(SG));
120    int T; scanf("%d", &T);
121    while(T--)
122    {
123        int n; scanf("%d", &n);
124
125        int nim=0;
126        for(int i=0; i<n; i++){
127            int x, y;
128            scanf("%d %d", &x, &y);
129            //nim ^= f(x, y);
130            nim ^= Nim_Multi(x, y);
131        }
132        if(nim){
133            printf("Have a try, lxhgww.\n");
134        }else{
135            printf("Don't waste your time.\n");
136        }
137    }
138    return 0;
139}