什么究极深奥博弈论啊，是不是被刻在神秘石头上了才这么神秘啊。
注意，以下定义都十分神秘，看不懂原理的话建议直接记。
推荐阅读：Nim积解法小结 - zjp_shadow，Nimber 系列略学习笔记 - chasedeath。
-
\(\text{Nim}\) 和
即异或运算。定义为 \(x \oplus y = \text{mex}\{\{a \oplus y \mid a \in [0,x)\} \bigcup \{x \oplus b \mid b \in [0,y)\}\}\)。
从这个定义上看，左边那个集合表示从状态 \(x\) 中取走任意个石子，然后再和右边异或成为新状态，右边集合同理，而根据 \(\text{SG}\) 函数的计算需要对这些后继状态取 \(\text{mex}\)。
所以运算结果相当于两个 \(\text{Nim}\) 游戏的和。
-
高维 \(\text{Nim}\) 游戏
一维：\(n\) 堆石子，轮流选一堆拿走任意非零个。
可以看作是数轴上撒 \(n\) 个黑点，其它都是白点，每次选一个黑点 \(a_i\)，再选一个 \(x \lt a_i\)，将线段 \(x \sim a_i\) 两端点颜色取反。
二维：平面上 \(n\) 个黑点，每次选一个 \((a_i,b_i)\) 再选一个 \((x \lt a_i,y \lt b_i)\)，将矩形 \((x,y) \sim (a_i,b_i)\) 四个顶点颜色取反。
三维：对应偏序上升到三维，将长方体八个顶点颜色取反。
以此类推，可以发现黑点之间是互不影响的，所以总状态就是黑点的 \(\text{Nim}\) 和。
-
\(\text{Nim}\) 积
定义二维 \(\text{Nim}\) 游戏中的 \(\text{Nim}\) 积：\(x \otimes y = \text{mex}\{(a \otimes b) \oplus (a \otimes y) \oplus (x \otimes b) \mid a \in [0,x),b \in [0,y)\}\)。
从博弈意义（？）上看比较好理解。
满足以下运算律：交换律，结合律，乘法分配律。同时 \(0 \otimes x = 0, 1 \otimes x = x\)。所以这两个运算在推导上完全可以当成加法和乘法处理。
由于这个东西十分复杂，暴力计算复杂度是 \(O((xy)^2)\)，非常优秀。
但是，经过伟大的数学家们不懈的努力，我们拥有了两个非常优秀的性质：
\[2^{2^{n}} \otimes x = 2^{2^{n}} \times x\;\;\;\;\text{where }x \lt 2^{2^{n}} \]\[2^{2^{n}} \otimes 2^{2^{n}} = \dfrac{3}{2} \times 2^{2^{n}} \]以上 \(n \in \mathbb{N}\)。证明不会。
考虑如何利用以上两个性质加速计算：
法一：
以下 \(\textbf{F}(x,y) = x \otimes y\)，\(\textbf{G}(x,y) = 2^x \otimes 2^y\)，“和” 表示 \(\text{Nim}\) 和，“积” 表示 \(\text{Nim}\) 积。
对于 \(x \text{ or }y \le 1\) 的情况特判，然后按位考虑，求出 \(x,y\) 每一位的积后求和即可。
对于 \(2^x \otimes 2^y\)，考虑拆分成若干 \(2^{2^{n}}\) 的积进行处理。
现在再对幂次 \(x,y\) 从高到低 按位考虑，求过的位就赋值为 \(0\)。设当前这一位是 \(2^k\)，如果都是 \(0\) 可以忽略，否则有两种情况：
- 都是 \(1\)，设 \(M = 2^{2^k},A = 2^{x-2^k},B = 2^{y - 2^k}\)，因为是最高位所以 \(M \gt A,B\)，所以 \(\textbf{G}(x,y) = (M \otimes A) \otimes (M \otimes B)\)，化简得 \(\textbf{G}(x,y) = \dfrac{3}{2}M \otimes \textbf{G}(x-2^k,y-2^k)\) ，那么递归即可；
- 其中一个为 \(1\)，钦定这个数是 \(x\) 否则
swap一下，则 \(M = 2^{2^k},A = 2^{x-2^{k}},B = 2^{y}\)，那么 \(\textbf{G}(x,y) = M \otimes \textbf{G}(x - 2^k,y)\)，还是递归计算即可。
直接按上面的写是可以的。把递归展开后分为两部分：
\[\textbf{G}(x,y) = (\otimes_{i \in \{x \text{ xor } y\}}2^{2^{i}}) \otimes (\otimes_{i \in \{x \text{ and } y\}}\dfrac{3}{2}2^{2^{i}}) \]前半部分根据性质直接整数乘法计算，后半部分用 \(\textbf{F}\) 递归算。
需要辨别一点，每次暴力计算 \(\textbf{G}\)，则总复杂度看起来是 \(O(\log x \log y \log \log x \log \log y)\)（或者可能是别的什么东西，但是肯定比下面的复杂度更高）。
注意到 \(\textbf{G}(x,y)\) 传入的参数都是 \(\log M\) 级别的，所以可以记忆化。
这样复杂度就是 \(O(\log x \log y)\)，但是好像跑得很慢。
感觉这里的复杂度还是不太会算，如果有佬算出来不对就去撅一撅评论区。
#define ForBit(i,x) for(ll i=0,n=x;1ll<<i<=n;++i) if(n>>i&1)
ll s[63][63]; inline ll f(ll x,ll y);
inline ll g(int x,int y){
if(!x||!y) return 1ll<<(x|y); if(s[x][y]!=-1) return s[x][y];
ll t=1; int upd=x^y; ForBit(i,upd) t<<=(1<<i);
upd=x&y; ForBit(i,upd) t=f(t,3ll<<((1<<i)-1));
return s[x][y]=s[y][x]=t;
}
inline ll f(ll x,ll y){
if(!x||!y) return 0; if(x==1||y==1) return max(x,y);
ll t=0; ForBit(i,x) ForBit(j,y) t^=g(i,j); return t;
}
法二：
考虑分治，设 \(k \in \mathbb{N}\) 为最小的满足 \(2^{2^{k+1}} \gt \max(x,y)\) 的值，\(x = 2^{2^{k}} x_0+x_1\)，\(y = 2^{2^{k}}y_0+y_1\)，则
为什么这样化简，因为 \(2^{2^{k}} \gt x_0,x_1,y_0,y_1\) 且 \(\dfrac{3}{2}2^{2^k} = 2^{2^k} \oplus 2^{2^k-1}\)。
这样所有的递归传入的参数都减小了一半，复杂度 \(O(\log x \log y)\)。
-
例题
洛谷翻译有没有素质？
题意：\(q\) 次询问 \(a[b,c]\) 按位异或 \(a[d,e]\) 的结果字典序是否小于 \(a[f,g]\)。\(n \le 5 \times 10^5\)，\(q \le 5 \times 10^4\)。
Sol：显然的哈希二分，难点在于哈希函数，我们需要设计一种函数使得 \(h(a \oplus b) = h(a) \oplus h(b)\)，其中 \(a,b\) 是等长序列。
考虑使用 \(\text{Nim}\) 数系，那么根据基础字符串哈希知识得到 \(h(a + \{x\}) = h(a) \otimes base \oplus x\)，并且显然满足上述条件。
于是你就切了一道满红 *3191 的题。复杂度 \(O(n \log^2 M + q \log n \log^2 M)\)。
说句闲话，法一会被卡 RE 。
inline ull NimProd(ull x,ull y,int p=64){
if(x<=1||y<=1) return x*y; if(p<=8&&(~s[x][y])) return s[x][y];
p>>=1; ull x0=x>>p,x1=x&((1ull<<p)-1),y0=y>>p,y1=y&((1ull<<p)-1),
xy0=NimProd(x0,y0,p),xy1=NimProd(x1,y1,p),xy=NimProd(x0^x1,y0^y1,p),
res=NimProd(xy0,1ull<<(p-1),p)^xy1^((xy1^xy)<<p);
assert((xy1^xy)<(1ull<<p));
if(p<8) s[x][y]=s[y][x]=res; return res;
}
inline ull Val(int l,int r){ return h[r]^NimProd(h[l-1],pw[r-l+1]); }
inline int LCP(int s1,int s2,int s3,int len){
int l=0,r=len,mid,ans=0;
while(l<=r) mid=l+r>>1,((Val(s1,s1+mid-1)^Val(s2,s2+mid-1))==Val(s3,s3+mid-1))?(ans=mid,l=mid+1):(r=mid-1);
return ans;
}
main(){
memset(s,-1,sizeof(s));
rd(n),rd(m),pw[0]=1,B=rnd();
for(int i=1;i<=n;++i)
rd(a[i]),h[i]=NimProd(h[i-1],B)^a[i],pw[i]=NimProd(pw[i-1],B);
while(m--){
int l1,r1,l2,r2,l3,r3,len1,len2;
rd(l1),rd(r1),rd(l2),rd(r2),rd(l3),rd(r3);
int lcp = LCP(l1,l2,l3,min((len1=r1-l1+1),(len2=r3-l3+1)));
if(lcp<min(len1,len2)) puts((a[l1+lcp]^a[l2+lcp])<a[l3+lcp]?"Yes":"No");
else puts(len1<len2?"Yes":"No");
}
}