Re：疑惑异或哈希
异或哈希是个很神奇的算法，利用了异或操作的特殊性和哈希降低冲突的原理，可以用于快速找到一个组合是否出现、序列中的数是否出现了 \(k\) 次
算法如其名，异或+哈希。
想起某首歌叫PPAP？
I have a \(\oplus\),I have an \(hash\).
(Uhh~) \(\oplus hash\) !
😅
异或
最基本的，也很重要的
考虑到异或运算满足交换律，即\(a \oplus b=b\oplus a\)
因此组合的不同排列的异或值相等
这样我们便可以忽略顺序，直接统计组合出现次数。
哈希
由于二进制位数有限，会存在一些情况使得异或并不正确，如：\(1\oplus 2=5\oplus 6\)，\(1\oplus 2\oplus 3 = 4\oplus 8\oplus 12\)
因此需要将原始数据哈希为较大的数降低冲突概率
应用
组合问题
直接来看道例题。
不会有人看不懂英文还不会拿软件翻译吧 虽然翻译软件翻译的跟构式一样
直接沿用异或哈希的思路，不难写出\(O(n^2)\)的代码
int n,m;mt19937_64 rnd(time(0));unsigned long long code[N],chk[N],Xor[N],a[N];signed main(){n=rd;for(int i=1;i<=n;i++){a[i]=rd;}for(int i=1;i<=n;i++){code[i]=rnd();chk[i]=chk[i-1]^code[i];}for(int i=1;i<=n;i++){Xor[i]=Xor[i-1]^code[a[i]];}int cnt=0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if((Xor[i-1]^Xor[j])==chk[j-i+1]){++cnt;}}}printf("%lld",cnt);return Elaina;}兴高采烈地交上去...乂~T了。
一看数据范围：\(3*10^5\)
好家伙\(O(n^2)\)肯定水过不去了。
进一步考虑到：
- 满足条件的区间肯定有\(1\)和等于区间长度的最大值\(max\)
分别向右/左做两次扩展：
设\(pos\)记录上一个\(1\)的位置，当前扩展到\(x\)
当\(x=1\)时，就更新指针\(pos\)，并重置\(mx\)
否则往回捯饬\(mx=max(mx,x)\)个数，异或哈希判断是否合法即可。
int n,m;int max(int a,int b){return a>b?a:b;}mt19937_64 rnd(time(0));unsigned long long code[N],chk[N],Xor[N],a[N];signed main(){n=rd;for(int i=1;i<=n;i++){a[i]=rd;}for(int i=1;i<=n;i++){code[i]=rnd();chk[i]=chk[i-1]^code[i];}for(int i=1;i<=n;i++){Xor[i]=Xor[i-1]^code[a[i]];}int cnt=0,pos=-1,cnt1=0,mx=0;for(int i=1;i<=n;i++){if(a[i]==1){pos=i,++cnt1,mx=1;}else if(pos!=-1){mx=max(mx,a[i]);if(i-mx+1<=pos)if((Xor[i]^Xor[i-mx])==chk[mx])++cnt;}}pos=-1;for(int i=n;i>=1;i--){if(a[i]==1){pos=i,++cnt1,mx=1;}else if(pos!=-1){mx=max(mx,a[i]);if(i+mx>=pos)if((Xor[i+mx-1]^Xor[i-1])==chk[mx])++cnt;}}printf("%lld",cnt+cnt1/2);return Elaina;}实际上反过来的时候可以直接reverse一下数组，然后再跑一遍，就不用复制粘贴打两遍了。。。
然后就 AC 了喵~
出现次数问题
二进制的异或的本质是对每一位进行不进位的加法，也就是每一位相加对2取模，即：
假设有一种运算\(③\)，使得\(a\ ③\ a\ ③\ a=0\)，即
其实也就是\(3\)进制的运算
扩展到\(k\)进制即可解决是否出现\(k\)次的问题
ull xork(ull a,ull b,int k){vector<int> vec;while(a||b){ vec.push_back((a+b)%k); a/=k; b/=k;}ull res=0;ull p=1;for(auto x:vec){ res+=p*x; p*=k;}return res;}ull xork(ull x,ull y,int k){int sum=0,p=1;//if(y%2==0) swap(x,y);while(x||y){sum+=(x%k+y%k)%k*p;p*=k;x/=k;y/=k;}return sum;}我们还是来看道例题
其实上一道题也可以在洛谷找到对应的翻译版本 （逃
首先我们知道一个思想，证明充要条件就要证明它既充分又必要；同样，要证明一个数等于某个值，必须让它既小于等于又大于等于这个值。
迁移到本题，我们让所有数的出现个数\(cnt = 3\)，便是要去满足\(cnt \geq 3 \land cnt \leq 3\)这俩约束
第一个约束随便糊一个异或哈希即可。
关键在于第二个约束。
我们考虑使用类似于双指针的算法：
考虑对于一个满足约束二的\([l, r]\)区间，右指针每次往右移动一次，都可能会破坏原本“满足约束二”的性质。那么为了让其重新满足，我们需要让左指针一直向右移动，即：从左到右删去数字使得区间再次满足约束二。
让新加入的右指针的值\(a_r\)出现的次数小于等于三即可；因为这样删除必然不会导致“因为其他数字出现次数减少而导致不能满足约束二”这种情况，理由显然。
令\(pre_r\)为\([1, r]\)的前缀异或和。
当删除完毕之后，我们统计满足\(pre_r = pre_{pos}\)且\(pos \in [l, r]\)的\(pos\) 数量，这一点可以使用 map 或者哈希表完成。
那么这道题就完成了，复杂度\(\mathcal{O}(N \log_2 N)\)或者纯线性。
然后关于...算了，自己看吧。
#include<bits/stdc++.h>using namespace std;#define int long long#define ll long long#define ull unsigned long long#define rd read()#define mkp make_pair#define psb push_back#define Elaina 0inline ll read(){ll f=1,x=0;char ch=getchar();for(;!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';return f*x;}const int mod=1e9+7;const int N=1e6+100;const int inf=0x7fffffff; int n,k; mt19937_64 rnd(time(0)); ull code[N],pre[N],a[N],num[N];map<ull,ull> mp; ull xork(ull x,ull y,int k){ull sum=0,p=1;while(x||y){sum+=(x%k+y%k)%k*p;p*=k;x/=k;y/=k;}return sum;} signed main(){srand(time(0));n=rd,k=3;for(int i=1;i<=n;i++){a[i]=rd;}for(int i=1;i<=N;i++){code[i]=rnd()%(1ll<<63);}for(int i=1;i<=n;i++){pre[i]=xork(pre[i-1],code[a[i]],k);}int cnt=0;mp[0]=1;for(int l=0,r=1;r<=n;++r){++num[a[r]];while(num[a[r]]>3){--num[a[l]];if(l>0) --mp[pre[l-1]];++l;}cnt+=mp[pre[r]];++mp[pre[r]];}printf("%lld",cnt);return Elaina;}\(x^2\)问题
判断一个序列的乘积是否是\(x^2\) ( $ x$ 为某个整数)
这个就比较好说了，根据唯一分解定理
其中，\(\alpha_1 \leq \alpha_2 \leq \alpha_3 \leq \dots \leq \alpha_k\)皆素数。
则
那么当这个序列质因子出现的次数都是偶数次即可。
练习
尾图
蒂蒂~❤ 嘿嘿嘿 我的蒂蒂❤