有些题目,我们需要判断一个区间某个元素出现的次数奇偶,如果元素的种类不多,我们可以使用异或哈希

1.炼金术士的配方(杭电2026春季联赛1)

你可以发现,a[i]<=1e6,质数的种类很少,所以我们可以给每一个质数随机分配一个不同的哈希值,如果区间异或值是0,那么这个区间合法

异或值生成代码:

mt19937_64 rnd(98275314);
int gen(){
    int x=0;
    while(x==0)
        x=rnd();
    return x;
}

本题代码

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int unsigned long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db  double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e6+10;
const int base=499;
int dcmp(double x){
   if(fabs(x)<eps){
      return 0;
   }
   return x<0?-1:1;
}
void debug(){
   cout<<"Test:Wrong"<<'\n';
   exit(0);
}
mt19937_64 rnd(98275314);
int gen(){
    int x=0;
    while(x==0)
        x=rnd();
    return x;
}
int prime[N],vis[N];
int cnt=0;
int len[N];
int Hash[N];
void init(){
    int n=1e6;
    for(int i=2;i<=n;i++){
         if(vis[i])continue;
         prime[++cnt]=i;
         Hash[i]=gen();
         for(int j=i;j<=n;j+=i){
             int sum=0; 
             int tmp=j;
             while(tmp%i==0){
                  tmp/=i;
                  sum=(sum+1)%2;
             }
             if(sum&&j!=i)Hash[j]^=Hash[i];
             vis[j]=1;
         }    
    }
}
void solve(){
   init();   
   int n,x;
   cin>>n>>x;   
   int hax=Hash[x];
   map<int,int>mp;
   mp[0]++;
   int ans=0;
   int pre=0;
   for(int i=1;i<=n;i++){
        int y;
        cin>>y;
        int hay=Hash[y];
        pre^=hay;
        ans+=mp[pre^hax];
        mp[pre]++;
   }
   cout<<ans<<'\n';
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T=1;
  //cin>>T;
  while(T--)solve();
  return 0;
}

2.小塔的序列(杭电2025春季联赛10)

相似度和题1很高