HDU-3404 Switch lights（NIM积）

小鱼儿 2022-06-10 06:09 99阅读 0赞

##                                Switch light  [HDU - 3404 ][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?

Input

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)

Output

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

Sample Input

2
    2
    1 2
    2 1
    2
    1 1
    2 2

Sample Output

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

找遍了好多地方，发现只有《从“k倍动态减法游戏”出发探究一类组合游戏问题》这个论文里有对NIM积的详细解释，然而我太笨了dalao的论文始终没看懂。

论文地址：http://www.doc88.com/p-5098170314707.html

从dalao处抄来了AC代码，感觉求NIM积就是个模板

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 300005;
    const int MOD = 1000000007;
    //const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    int sg[20][20];
    int f(int, int);//声明一下，因为f与g互相嵌套调用
    int g(int x, int y)//计算2^x与2^y的nim积
    {
    	if (sg[x][y] != -1)//查备忘录
    	{
    		return sg[x][y];
    	}
    	if (!x)//x==0也就是1与2^y的nim积，等于2^y
    	{
    		return sg[x][y] = 1 << y;
    	}
    	if (!y)//同上
    	{
    		return sg[x][y] = 1 << x;
    	}
    	int ans = 1, k = 1, t;
    	int x1 = x, y1 = y;
    	while (x || y)//再将x和y分为二进制，这里计算那些普通乘积的（即对应二进制位不同的）
    	{
    		t = 1 << k;//从此位得到的最终的数2^k
    		if ((x & 1 || y & 1) && !((x & 1) && (y & 1)))//该位不同
    		{
    			ans *= t;
    		}
    		x >>= 1;
    		y >>= 1;
    		k <<= 1;//从此位得到的指数(本身也是2的幂)
    	}
    	k = 1;
    	x = x1;
    	y = y1;
    	while (x || y)//计算那些相同的fermat 2-power 数，与已得出的数的nim积
    	{
    		t = 1 << k;
    		if ((x & 1) && (y & 1))//该位相同
    		{
    			ans = f(ans, t / 2 * 3);
    		}
    		x >>= 1;
    		y >>= 1;
    		k <<= 1;//从此位得到的指数(本身也是2的幂)
    	}
    	return (sg[x1][y1] = 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和y分解后）按分配律计算其积
    	{
    		if ((i & 1) == 0)continue;//该位（bit）是1才计算，否则跳过
    		for (int j = y, b = 0; j; j >>= 1, b++)
    		{
    			if ((j & 1) == 0)continue;
    			ans ^= g(a, b);
    		}
    	}
    	return ans;
    }
    int main()
    {
    	int x, y, t;
    	int n, ans;
    	scanf("%d", &t);
    	while (t--)
    	{
    		memset(sg, -1, sizeof(sg));
    		scanf("%d", &n);
    		ans = 0;
    		while (n--)
    		{
    			scanf("%d%d", &x, &y);
    			ans ^= f(x, y);
    
    		}
    		puts(ans ? "Have a try, lxhgww." : "Don't waste your time.");
    	}
    	return 0;
    }

[HDU - 3404]: https://vjudge.net/problem/14696/origin