Nim 积

· · 个人记录

什么究极深奥博弈论啊，是不是被刻在神秘石头上了才这么神秘啊。

注意，以下定义都十分神秘，看不懂原理的话建议直接记。

推荐阅读：Nim积解法小结 - zjp_shadow，Nimber 系列略学习笔记 - chasedeath。

即异或运算。定义为 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} 游戏的和。

一维：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} 积：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. 都是 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) ，那么递归即可；
  2. 其中一个为 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)，但是好像跑得很慢。

感觉这里的复杂度还是不太会算，如果有佬算出来不对就去撅一撅评论区。/kel 

#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，则

&=[\dfrac{3}{2}2^{2^{k}} \otimes (x_0 \otimes y_0)] \oplus [2^{2^{k}} \otimes (x_0 \otimes y_1 \oplus x_1 \otimes y_0)] \oplus (x_1 \otimes y_1)\\ &=x_1 \otimes y_1 \oplus 2^{2^{k}}[(x_0 \oplus x_1) \otimes (y_0 \oplus y_1) \oplus x_1 \otimes y_1]\oplus 2^{2^{k}-1} \otimes x_0 \otimes y_0\end{aligned}

为什么这样化简，因为 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)。

  1. [ABC274Ex] XOR Sum of Arrays

洛谷翻译有没有素质？

题意：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。/qd 

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");
    }
}