【学习笔记】[ABC274Ex] XOR Sum of Arrays

有点难😅

真的是$ABC$的难度吗😅

非常精妙的哈希题目。

定义矩阵乘法：$c_{i,j}=\oplus (a_{i,k}\&b_{k,j})$

之所以可以矩阵乘法是因为满足 $(a\oplus b)\&c=(a\&c)\oplus (b\&c)$

其实非常好验证，就把两个运算符按顺序写下来，然后把括号拆开，看等式两边是否恒等即可。

定义对于序列 { a i } \{a_i\} {ai​}的哈希规则为，将每个$a_k$与上$k-1$个$p$后的结果全部异或起来

因为$(a\oplus b)\&p=(a\&p)\oplus (b\&p)$，所以如果$c_i=a_i\oplus b_i$，那么 { c i } \{c_i\} {ci​}的哈希值就是把 { a i } \{a_i\} {ai​}和 { b i } \{b_i\} {bi​}对应的哈希值异或起来

但是发现与上的$p$都是相同的，所以这个方案冲突的概率很大

仔细观察正解的代码，发现他是把$p$设计成了一个$M\times M$的 $01$矩阵 （其中$M$表示二进制位数，也就是$64$），$a_i$看成一个长度为$M$的 $01$向量 ，这个向量的第$i$位就是$a_i$在二进制下的第$i$位

不妨形式化的写一下，首先我们随机一个矩阵$p$，哈希值就是${\oplus }_{i=1}^n{v}_i{p}^{i-1}$。发现$c_i=a_i\oplus b_i$那不就是把两个向量做按位异或吗。

直接倍增的复杂度是$O(n{M}^3\log n)$，考虑优化。

注意到是$01$矩阵，所以可以把同一行压成一个$64$位整数，这样转移优化到了$O(M^2)$。

最终复杂度$O(n{M}^2\log n)$。瓶颈在于倍增预处理，不知道可不可以做的更好。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define ull unsigned long long
using namespace std;
const int N=5e5+5;
const int M=64;
mt19937_64 t(time(0));
struct Matrix{ull c[M];Matrix(){memset(c,0,sizeof c);}Matrix operator *(const Matrix &a)const{Matrix r;for(int i=0;i<M;i++){for(int j=0;j<M;j++){if(c[i]>>j&1){r.c[i]^=a.c[j];}}}return r;}
}pw[20];
int n,m;
ll a[N];
ull st[N][20];
ull get(ull x,Matrix y){ull res(0);for(int i=0;i<M;i++){if(x>>i&1)res^=y.c[i];}return res;
}
void write(ull x){if(x<10){cout<<(char)('0'+x);return;}write(x/10),cout<<(char)('0'+x%10);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;srand(time(0));for(int i=1;i<=n;i++)cin>>a[i],st[i][0]=a[i];for(int i=0;i<M;i++){pw[0].c[i]=t();}for(int i=1;i<20;i++)pw[i]=pw[i-1]*pw[i-1];for(int j=1;j<20;j++){for(int i=1;i<=n-(1<<j)+1;i++){st[i][j]=st[i][j-1]^get(st[i+(1<<j-1)][j-1],pw[j-1]);}}for(int i=1;i<=m;i++){int b,c,d,e,f,g;cin>>b>>c>>d>>e>>f>>g;for(int j=19;j>=0;j--){if(b+(1<<j)-1<=c&&f+(1<<j)-1<=g&&(st[b][j]^st[d][j])==st[f][j]){b+=(1<<j),d+=(1<<j),f+=(1<<j);}}if(b>c){if(f>g)cout<<"No"<<"\n";else cout<<"Yes"<<"\n";}else{if(f>g)cout<<"No"<<"\n";else if((a[b]^a[d])<a[f])cout<<"Yes"<<"\n";else cout<<"No"<<"\n";}}
}