CodeForces-1800F 题解

发表于2023-11-05更新于2023-11-05

题目传送门

一道字符串题……

既然两个字符串拼接后有一种字符不能出现，那么可以枚举这个字符，我们就只需要关注没有出现过这种字符的字符串了。

剩下的字符串仅会出现 2525 种字符，而我们并不关心字符串里字符的顺序，仅关心字符出现的个数的奇偶性，因此我们可以把字符串看做是一个长度为 2525 的二进制数 xix_i，如果某一位为 11 表明这种字符在字符串中的出现次数为奇数，如果某一位为 00 则表明为偶数。

那么接下来题目就转变为有多少对 i,ji,j 满足 xi⊕xj=225−1x_i\oplus x_j =2^{25}-1，可以使用 std :: map 统计。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

const long long IMX = 1ll << 30;
const long long LMX = 1ll << 60;

typedef long long ll;
typedef __int128 i128;
typedef long double ld;
typedef __float128 f128;

namespace xvl_ { 
    #define SP(n, x) std :: setprecision(n) << std :: fixed << x
    #define REP(i, l, r) for (auto i = (l); i <= (r); i ++)
    #define PER(i, r, l) for (auto i = (r); i >= (l); i --)
    #define DEBUG(x) std :: cerr << #x << " = " << x << '\n'
    template <typename T> T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
    template <typename T> T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;
ll n, ans;
ll cnt[200005][26];
string s[200005];
vector <ll> x;
map <ll, ll> mp;
int main() {
    // freopen("InName.in", "r", stdin);
    // freopen("OutName.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    REP(i, 1, n) {
        cin >> s[i];
        REP(j, 0, s[i].size() - 1) cnt[i][s[i][j] - 'a'] ++;
    }
    REP(c, 0, 25) {
        mp.clear(), x.clear();
        REP(i, 1, n) {
            if (cnt[i][c]) continue;
            x.push_back(0);
            REP(j, 0, 25) {
                if (j == c) continue;
                x[x.size() - 1] = (x[x.size() - 1] << 1) | (cnt[i][j] & 1);
            }
        }
        for (auto v : x) {
            mp[v] ++;
            ans += mp[v ^ (1 << 25) - 1];
        }
    }
    cout << ans;
    return 0;
}