【异或哈希】CF855 div3 F

矫情吗；* 2024-03-26 17:40 116阅读 0赞

**感觉这道题跟之前有一题特别像，都是异或哈希**

**感觉这种题应该很典，记录一下**

[(66条消息) Codeforces Round \#841 (Div. 2) and Divide by Zero【异或差分+动态map维护】 2022 C. Even Subarrays\_lamentropetion的博客-CSDN博客][66_ Codeforces Round _841 _Div. 2_ and Divide by Zero_map_ 2022 C. Even Subarrays_lamentropetion_-CSDN]

[Problem - F - Codeforces][]

题意：

给你n个字符串，求对 (i, j) 的数量，使得

c\[i\] = s\[i\] + s\[j\] （两个字符串串联起来）

1.c\[i\]的长度为奇数

2. c\[i\] 所包含的字符种类恰好是 25 个

3. c\[i\] 所包含的每种字符的出现次数都为奇数

思路：

首先，目标状态是不确定的，不知道目标状态少哪个字符，因此我们去枚举少了哪个字符

当2和3都满足时，1一定满足

确定完目标状态之后，注意到我们要去n^2枚举两个指针，那么按照套路的做法，**我们去枚举其中一个指针，然后去考虑限定条件来得到另一个指针**

它的限定条件和全局的哈希有关，因此我们去**维护全局的哈希**

那么，全局的哈希去维护什么值呢？很明显是去维护每个字符是否出现以及每个字符的出现次数的奇偶性

a\[i\]表示每个字符串中每个字符是否出现，b\[i\]表示每个字符串中字符的出现次数的奇偶性

所以在枚举之前，可以先去预处理这两个哈希

考虑去枚举i，确定了两个字符串连起来的状态，我们怎么去确定j

即s\[j\]的限定条件是什么

1.  每种字符出现次数为奇数

1.  s\[i\]和s\[j\]的字符种类加起来必须有25种

假设 s\[i\] 对应的 b\[i\] 是 k，和法的 c\[i\] 对应的 b\[i\] 是 q, s\[j\] 对应的 b\[j\] 是 p，那 s\[i\] + s\[j\] 对应的 b\[i\] 其实就是 k^p

因此直接去维护动态map就能计数出所有满足条件的对数

当然不能忘记清空cnt数组

Code:

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <map>
    #include <queue>
    #include <set>
    //#define int long long
    using namespace std;
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    string s;
    int n;
    int a[mxn],b[mxn],cnt[1<<26];
    void solve(){
        s.clear();
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(cnt,0,sizeof(cnt));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>s;
            for(int j=0;j<s.size();j++){
                a[i]|=(1<<(s[j]-'a'));
                b[i]^=(1<<(s[j]-'a'));
            }
        }
        i64 ans=0;
        for(int i=0;i<26;i++){
            int S=(1<<26)-1-(1<<i);
            for(int j=1;j<=n;j++){
                if(!((a[j]>>i)&1)){
                    cnt[b[j]]++;
                    ans+=cnt[S^b[j]];
                }
            }
            for(int j=1;j<=n;j++){
                if(!((a[j]>>i)&1)){
                    cnt[b[j]]--;
                }
            }
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[66_ Codeforces Round _841 _Div. 2_ and Divide by Zero_map_ 2022 C. Even Subarrays_lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/128470334
[Problem - F - Codeforces]: https://codeforces.com/contest/1800/problem/F