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) 满足
- 对于(x<a) ,有 (a otimes b = a imes b)
- (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://codeforces.com/blog/entry/74214
计算 (x otimes y) ,设 (x=xa cdot P+xb,y=ya cdot P + yb) ,其中 (P) 是一个尽量将 (x,y) 分为相同两半的费马数.
那么有
观察发现,对于其中 ((xa otimes yb) oplus (xb otimes ya)) ,有
而 (P otimes P = dfrac 32 P = P oplus dfrac P2) .所以可以如下计算
ull nim[256][256]; // 记忆化
ull f(ull x,ull y,int len=32) {
if(x==0||y==0) return 0;
if(x==1||y==1) return x*y;
if(len<=4&&nim[x][y]) return nim[x][y];
ull xa=x>>len,xb=x^(xa<<len),ya=y>>len,yb=y^(ya<<len);
ull a=f(xb,yb,len>>1),b=f(xa^xb,ya^yb,len>>1),c=f(xa,ya,len>>1),d=f(c,1ull<<len-1,len>>1);
ull re=((b^a)<<len)^a^d;
if(len<=4) nim[x][y]=re;
// debug("%llu %llu %llu
",x,y,re);
return re;
}
由于 (x,y) 很快会变成 (0) ,所以速度远远快于上面的方法.