仍在深渊妄想得到你的回望

· · 题解

下文中令 w=32（a_i 的字长），记 \oplus 为异或运算，\otimes 为 Nim 积。

Nim 积是个啥组合意义咱不用知道，但我们会用到它的两条性质：

(x\oplus y)\otimes z=(x\otimes z)\oplus(y\otimes z) \forall n\in \Z_+,x\in [0,2^{2^n})\cap \Z,F(x,{2^{2^{n}}})=x

其中 F(x,y)=\begin{cases}x & y=1 \\ x^{y-1}\otimes x & y>1\end{cases}。

第一条性质告诉我们 (x\oplus y)\otimes(x\oplus y)=(x\otimes x)\oplus(y\otimes y)，这样可以发现我们对一个区间内所有数操作后异或和等价于对其异或和进行操作，第二条性质告诉我们一个数操作 2^n=w=32 次等于不操作。

维护异或和是简单的。维护总和的话可以维护目前序列操作 0\sim 31 次的和，每次旋转一下数组即可。

还有个“小”问题是我们不能求 x\otimes x。把 x 拆成一堆 2 的幂之和，之后你可以用一些神秘算法把这 32 个值搞出来，或者 OEIS，当然也可以去下面代码里拷过来。

对求值的过程进行一些优化，预处理高 w/2 位和低 w/2 位的所有情况。

（如果你把 2^x\otimes 2^x 当作常量扔进去的话）复杂度为 O((n+m\log n+2^{w/2})w)。

//Happy Birthday, Ling Luo!
#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull unsigned long long
#define lson (u<<1)
#define rson (u<<1|1)
#define nxt(x) T[x>>16]^t[x&65535u]
#define NXT(x,k) TO[x>>16][k]^to[x&65535u][k]
const uint N=250007,M=65536,NIM[32]={1u,3u,6u,13u,24u,52u,103u,222u,384u,832u,1648u,3552u,6237u,13563u,26511u,56906u,98304u,212992u,421888u,909312u,1596672u,3472128u,6786816u,14567936u,25190110u,54589881u,108036850u,232800673u,408783316u,888883132u,1737454078u,3729449897u};
int n,m,op,l,r,tag[N<<2];
uint a[N],T[M],t[M],TO[M][32],to[M][32],val[N<<2];
ull sum[N<<2][32];
void add(int u,int v){val[u]=NXT(val[u],v);rotate(sum[u],sum[u]+v,sum[u]+32);tag[u]=tag[u]+v&31;}
void pushup(int u){
    val[u]=val[lson]^val[rson];
    for (int i=0;i<32;++i) sum[u][i]=sum[lson][i]+sum[rson][i];
}
void pushdown(int u){
    if (tag[u]){
        add(lson,tag[u]);add(rson,tag[u]);tag[u]=0;
    }
}
void build(int u,int l,int r){
    if (l==r){
        val[u]=a[l];
        for (int i=0;i<32;++i) sum[u][i]=NXT(a[l],i);
        return;
    }
    int mid=l+r>>1;
    build(lson,l,mid);build(rson,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,int L,int R){
    if (L<=l&&r<=R){add(u,1);return;}
    int mid=l+r>>1;pushdown(u);
    if (L<=mid) modify(lson,l,mid,L,R);
    if (R>mid) modify(rson,mid+1,r,L,R);
    pushup(u);
}
uint query1(int u,int l,int r,int L,int R){
    if (L<=l&&r<=R) return val[u];
    int mid=l+r>>1;pushdown(u);
    if (R<=mid) return query1(lson,l,mid,L,R);
    if (L>mid) return query1(rson,mid+1,r,L,R);
    return query1(lson,l,mid,L,R)^query1(rson,mid+1,r,L,R);
}
ull query2(int u,int l,int r,int L,int R){
    if (L<=l&&r<=R) return sum[u][0];
    int mid=l+r>>1;pushdown(u);
    if (R<=mid) return query2(lson,l,mid,L,R);
    if (L>mid) return query2(rson,mid+1,r,L,R);
    return query2(lson,l,mid,L,R)+query2(rson,mid+1,r,L,R);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    for (int i=0;i<16;++i){t[1<<i]=NIM[i];T[1<<i]=NIM[i+16];}
    for (uint i=0;i<M;++i){
        if (i&i-1){T[i]=T[i&i-1]^T[i&-i];t[i]=t[i&i-1]^t[i&-i];}
        TO[i][0]=i<<16;to[i][0]=i;
    }
    for (int i=0;i<M;++i) for (int j=1;j<32;++j){TO[i][j]=nxt(TO[i][j-1]);to[i][j]=nxt(to[i][j-1]);}
    cin>>n>>m;
    for (int i=1;i<=n;++i) cin>>a[i];
    build(1,1,n);
    while(m--){
        cin>>op>>l>>r;
        if (op==1) modify(1,1,n,l,r);
        else if (op==2) cout<<query1(1,1,n,l,r)<<'\n';
        else cout<<query2(1,1,n,l,r)<<'\n';
    }
    return 0;
}

考虑到官方题解默认你会这玩意但显然大部分人不会，还是解释一下 nim product 的求法吧。

先二进制拆位。由 nim product 的性质，假设 A=\bigoplus_1^n2^{a_i},B=\bigoplus_1^m2^{b_i}，则由分配律，A\otimes B=\bigoplus_1^n \bigoplus_1^m(2^{a_i}\otimes 2^{b_i})。

拆完位之后就转化成了处理 A=2^x\otimes 2^y(x\ge y)。尝试递推。

第一种情况是 y=0，显然此时 A=2^x，你可以直接模拟一下题目中的式子。

然后就要用到性质：

\forall\ x<2^{2^n},2^{2^n}\otimes x=2^{2^n}\cdot x 2^{2^n}\otimes 2^{2^n}=2^{2^n}\oplus 2^{2^n-1}

据此我们可以处理 x=2^k 的情况。

接下来我们把 x 和 y 的最高二进制位拉出来，假设其为 2^a 和 2^b。此时 x\ne 2^a（已经在前面处理了这种情况）。

如果 a=b，则由结合律，2^x\otimes 2^y=(2^{2^a}\otimes 2^{2^b})\otimes (2^{x-2^a}\otimes 2^{x-2^b})，后面那玩意已经递推得到了且其 <2^{2^a}（也是性质），设它为 z，前面那一部分就是 2^{2^a}\oplus 2^{2^a-1}，所以 2^x \otimes 2^y = (2^{2^a}\oplus 2^{2^a-1})\otimes z=(2^{2^a}\otimes z)\oplus(2^{2^a-1}\otimes z)，全部预处理到了，拆位做即可。

如果 a>b，此时 2^x\otimes 2^y=2^{2^a}\otimes (2^{2^b}\otimes (2^{x-2^a}\otimes 2^{x-2^b}))，还是设最后一部分为 z，此时 2^{2^b}\otimes z 可以拆位做，因为后面三个数小于 2^{2^a}，它们 \otimes 后的结果也小于 2^{2^a}，用前面的性质，直接将其乘上 2^{2^a} 即可。

然后我们就得出了一个快速递推的算法，时间复杂度为 O(w^3)。

代码（可以打出表后像我一样拷进程序里，也可以把它复制在程序最前面）：

#include<bits/stdc++.h>
using namespace std;
const int N=32;
unsigned int NIM[N][N];
int main(){
    for (int i=0;i<N;++i) for (int j=0;j<=i;++j){
        if (i==0||j==0){NIM[i][j]=NIM[j][i]=1u<<i+j;continue;}
        if (!(i&i-1)){
            if (i==j) NIM[i][j]=(1<<i)+(1<<i-1);
            else NIM[i][j]=NIM[j][i]=(1u<<i+j);
            continue;
        }
        int a=__lg(i),b=__lg(j);
        unsigned int x=i^(1u<<a),y=j^(1u<<b);
        if (a==b){
            x=NIM[x][y];
            for (int l=0;l<N;++l) if ((x>>l)&1) NIM[i][j]^=NIM[l][1u<<a]^NIM[l][(1u<<a)-1];
            NIM[j][i]=NIM[i][j];
            continue;
        }
        x=NIM[x][y];
        for (int l=0;l<N;++l) if ((x>>l)&1) NIM[i][j]^=NIM[l][1<<b];
        NIM[j][i]=NIM[i][j]=(1<<(1<<a))*NIM[i][j];
    }
//  for (int i=0;i<N;++i){for (int j=0;j<N;++j) cout<<NIM[i][j]<<' ';cout<<endl;}
    for (int i=0;i<N;++i) cout<<NIM[i][i]<<endl;
    return 0;
}