题目描述

难度分:$1900$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的字符串数组$a$，只包含小写英文字母，字符串长度之和$\leq 5 \times 10^6$。

遍历所有的$(i,j)$，满足$0 \leq i \leq j \lt n$。
设$s=a[i]+a[j]$，如果$s$能同时满足如下三个要求，则把答案加一：

1. $s$的长度是奇数。
2. $s$恰好包含$25$种不同字母。
3. 每种字母的出现次数均为奇数。

输出答案。

输入样例

10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz

输出样例

5

算法

状态压缩+哈希表统计

从来没有这么快切出过周四的题目，今天本来还感觉会超时，结果直接过了。

状态压缩

首先考虑长度限制，要想两个串拼起来以后长度是奇数，那两个串的长度肯定是一奇一偶。其次考虑拼接后必须出现$25$种字母，每个字符串需要用两个状态码来表示，$mask_1$表示某个串中各个字母出现的频数奇偶性（奇数频数的字母对应的位是$1$），$mask_2$表示某个串中各个字母是否出现过（出现过的字母对应位是$1$）。

统计

构建一个哈希表$odd$，$key$为$(mask_1,mask_2)$，$value$为频数，存储奇数长度的字符串信息。构建一个哈希表$even$，存储偶数长度的信息，结构为“$mask_1 \rightarrow mask_2 \rightarrow$频数”。遍历一遍字符串数组就可以得到这两个哈希表。

1. 然后遍历$odd$表，每个状态$(mask_{i1},mask_{i2})$代表$a[i]$。
2. 再枚举缺失的字母，假如缺失的是第$c$个字母（从$0$开始），则$a[i]+a[j]$的状态应该为$target=(2^{26}-1) \oplus 2^c$，$a[j]$的状态一$mask_1$应该为$mask_{j1}=target \oplus mask_{i1}$。
3. 在$mask_{j1}$存在于$even$表的情况下，遍历$even[mask_{j1}]$，从中找到满足$target=mask_{i2} \lor mask_{j2}$的状态二$mask_2=mask_{j2}$即可。

因此，最终答案就是所有$odd[(mask_{i1},mask_{i2})] \times even[mask_{j1}][mask_{j2}]$的累加和。

复杂度分析

时间复杂度

遍历$a$数组获得$odd$和$even$两个哈希表的时间复杂度为$O(\Sigma n)$（为了方便，代码实现中$odd$用的有序表，但分析时间复杂度按照哈希表来分析），其中$\Sigma$表示字符集的大小，本题中$\Sigma=26$。

接下来统计答案，因为在遍历数组$a$时，每次循环计算字符串的状态只会对$odd$和$even$操作一次，所以$odd$和$even$中的状态总量应该是$O(n)$级别。在统计时即使双重循环遍历$odd$和$even$，由于受到状态匹配的限制，时间复杂度应该还是线性的（有待严格证明），最后算上枚举缺失字母的时间，这个过程的时间复杂度大概还是$O(\Sigma n)$。

综上，算法整体的时间复杂度为$O(\Sigma n)$。

空间复杂度

空间消耗的瓶颈就是$odd$和$even$两个哈希表，它们在最差情况下会有$O(n)$级别的键值对，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <unordered_map>
#pragma GCC optimize(2)

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int n;

int main() {
    scanf("%d", &n);
    map<PII, int> odd;
    unordered_map<int, unordered_map<int, int>> even;
    string s;
    for(int i = 0; i < n; i++) {
        cin >> s;
        int mask1 = 0, mask2 = 0;
        for(char c: s) {
            mask1 ^= 1<<(c - 'a');
            mask2 |= 1<<(c - 'a');
        }
        int len = s.size();
        if(len&1) {
            odd[{mask1, mask2}]++;
        }else {
            even[mask1][mask2]++;
        }
    }
    LL ans = 0;
    for(auto&[pir, cnt1]: odd) {
        int temp = (1<<26) - 1;
        int mask_i1 = pir.first, mask_i2 = pir.second;
        for(int i = 0; i < 26; i++) {
            int target = temp ^ (1<<i);
            int mask_j1 = target ^ mask_i1;
            if(even.find(mask_j1) != even.end()) {
                for(auto&[mask_j2, cnt2]: even[mask_j1]) {
                    if((mask_i2|mask_j2) == target) {
                        ans += (LL)cnt1*cnt2;
                    }
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}