发布时间：2024-07-31

异或哈希

判断一个区间是否与另外一个区间相等

CF1418G(判断一个有多少个子序列所有数出现恰好3(k)次)

• 对于每种不同的数，赋值一个哈希值
• 这里使用加减代替异或达到相同效果
• 具体来讲，对于如果出现了k次，那么就是变成-(k-1)次，那么如果前面出现了k-1次，相加就会等于0

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1),nums,freq(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++)a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
    vector<ULL> h(n+1),rdm(n+1);
    for(int i=0;i<=n;i++)rdm[i]=rng();
    vector<int> fre(n+1);
    for(int i=1;i<=n;i++){
        h[i]=h[i-1];
        h[i]-=fre[a[i]]*rdm[a[i]];
        (fre[a[i]]+=1)%=k;
        h[i]+=fre[a[i]]*rdm[a[i]];
    }
    fre.assign(n+1,0);
    unordered_map<ULL,int> cnt;
    cnt[0]=1;
    int ans=0;
    for(int i=1,j=0;i<=n;i++){
        fre[a[i]]++;
        while(fre[a[i]]>k){
            fre[a[j]]--;
            cnt[h[j-1]]--;
            j++;
        }
        ans+=cnt[h[i]]++;
    }
    cout<<ans<<"\n";
}