[CF383E] Vowels 题解
思路
要求的这个东西一看就没什么性质,考虑枚举所有元音子集。
如果我们能够求出 \(f_s\) 表示 \(s\) 集合作为元音时有多少个单词至少包含一个元音。
难求,正难则反,考虑 \(f_s\) 表示 \(s\) 集合作为元音时有多少个单词全都由非元音字母组成,由于对称性,我们只需要求出 \(s\) 集合作为非元音时有多少个单词全都由非元音字母组成,这个就是权值为 01 的子集和,SOSDP 即可。
时间复杂度:\(O(2^{\Sigma}\Sigma)\)。
// Problem: Vowels
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-02-04 16:29:01
#include <iostream>
#define int long long
using namespace std;
const int N = 1e4 + 10, M = 24;
int n, f[(1 << M)];
string s;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1, x; i <= n; i ++) {
cin >> s, x = 0;
for(auto c : s) x |= (1 << (c - 'a'));
f[x] ++;
}
for(int j = 0; j < 24; j ++)
for(int i = 1; i < (1 << 24); i ++)
if(i >> j & 1) f[i] += f[i ^ (1 << j)];
int ans = 0;
for(int i = 0; i < (1 << 24); i ++)
ans ^= (n - f[i]) * (n - f[i]);
cout << ans << '\n';
return 0;
}
标签:int,题解,Vowels,单词,元音,CF383E
From: https://www.cnblogs.com/MoyouSayuki/p/18006671