链接：https://codeforces.com/contest/383/problem/E
思路：字符一共24种，那么就有种可能的元音子集，考虑对于每一个单词并更新子集，这里需要用到容斥。有x个元素的状态的个数 = 有1个 - 有2个 + 有3个…. + ，那么我们可以用sosdp来计算这个前缀和，最后统计一下答案即可。
代码：
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
|
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vp;
const int inf = 1e9;
const ll INF = 1e18;
const db eps = 1e-10;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ep emplace
#define mem(a) memset(a, 0, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(b))
#define PA cout << "passn"
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define TM cout << db(clock()) / CLOCKS_PER_SEC << 'n'
const int maxn = 1 << 24;
int f[maxn], a[maxn], n;
char s[20];
int () {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%s", s);
int p = 0;
for (int j = 0; j < 3; j++) p |= 1 << (s[j] - 'a');
for (int j = p; j; j = (j - 1) & p) {
if (__builtin_popcount(j) & 1) a[j]++;
else a[j]--;
}
}
for (int i = 0; i < (1 << 24); i++) f[i] = a[i];
for (int j = 0; j < 24; j++) {
for (int i = 0; i < (1 << 24); i++) {
if (i >> j & 1) f[i] += f[i ^ (1 << j)];
}
}
int res = 0;
for (int i = 0; i < (1 << 24); i++) res ^= 1ll * f[i] * f[i];
printf("%dn", res);
return 0;
}
|
近期评论