Nim积

https://www.cnblogs.com/zjp-shadow/p/10507030.html

对于高维的Nim游戏,可以拆分为单独的每一维求Nim积.

下文以二维Nim积为例,定义为

其中 \(\otimes\) 为nim积, \(\oplus\) 为异或.

性质

即 \(0\) 与任何数的Nim积为 \(0\) ,\(1\) 为单位元,满足交换律,结合律,分配率.

费马数

费马数即 Fermat 2-power 数为形如 \(2^{2^n}\) 的数,其中 \(n \in \mathbb {N}\) ,对于费马数 \(a\) 满足

1. 对于\(x<a\) ,有 \(a \otimes b = a \times b\)
2. \(a \otimes a = \dfrac 32 a\)

二维Nim积的计算

设 \(f(x,y) = x \otimes y\) ,我们将 \(x,y\) 拆分为若干个二进制位计算,令 \(g(x,y) = 2^x \otimes 2^y\) ,则有

\(g(x,y)\) 的计算

现在要计算 \(g(x,y)=2^x \oplus 2^y\) ,那么对于 \(x,y\) 的最高位 \(k\) (即 \(x\) 的最高位和 \(y\) 的最高位中的较大值),有以下两种情况

最高位均为1

设 \(M=2^{2^k},A=2^{x-2^k},B=2^{y-2^k}\) ,其中 \(M\) 为费马数,且 \(M>A,M>B\) ,那么可以利用费马数的性质进行如下推导

最高位中有一个1,一个0

不妨设是 \(x\) 的最高位为 \(1\) ,设 \(M=2^{2^k},A=2^{x-2^k},B=2^y\) ,有 \(M>A,M>B\) ,则

于是递归的思考上面的过程,可以得到这样的式子

右边的部分可以用 \(f(x,y)\) 进行递归计算

时间复杂度 \(O(\log ^2 n)\) .

HDU 3404 Switch lights

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const int maxn=1000+50;
int T;
int n;
int x[maxn],y[maxn];
int bit[25];
int g[25][25];
int F(int,int);
int G(int x,int y)
{
	if(x==0||y==0) return bit[x+y];
	if(~g[x][y]) return g[x][y];
	int &re=g[x][y]=1;
	for(int i=0,t=x^y;bit[i]<=t;++i) if(t&bit[i])
		re<<=bit[i];
	for(int i=0,t=x&y;bit[i]<=t;++i) if(t&bit[i])
		re=F(re,3*bit[bit[i]-1]);
	return re;
}
int F(int x,int y)
{
	if(!x||!y) return 0;
	if(x==1||y==1) return x*y;
	int re=0;
	for(int i=0;bit[i]<=x;++i) if(x&bit[i])
		for(int j=0;bit[j]<=y;++j) if(y&bit[j])
			re^=G(i,j);
	return re;
}
bool sol()
{
	int an=0;
	for(int i=1;i<=n;++i) an^=F(x[i],y[i]);
	return an;
}
void init()
{
	bit[0]=1;
	for(int i=1;i<=20;++i) bit[i]=bit[i-1]<<1;
	memset(g,-1,sizeof(g));
}
int main()
{
	init();
	scanf("%d",&T);
	for(int kase=1;kase<=T;++kase)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]);
		puts(sol()?"Have a try, lxhgww.":"Don‘t waste your time.");
	}
	return 0;
}

Nim积

原文：https://www.cnblogs.com/ljzalc1022/p/12897376.html