CF383E Vowels

LuoGu: CF383E Vowels

CF: E. Vowels

对于每一个元音字母集合 $a$ ，每一个单词 $b$ ，如果 a & b > 0 则为合法，那么 a & b = 0 则为不合法。考虑不合法的情况，对于一个元音字母集合 $a$ ，其取反后含有子集 $b$ 则 $b$ 贡献，可以用高维前缀和做。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1 << 24;
int n, f[N];
int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
    {
        int x = 0;
        char s[5];
        scanf("%s", s);
        for (int j = 0; j < 3; j++)
            s[j] <= 'x' && (x |= 1 << s[j] - 'a');
        f[x]++;
    }
    for (int i = 0; i < 24; i++)
        for (int j = 0; j < 1 << 24; j++)
            j >> i & 1 && (f[j] += f[j ^ 1 << i]);
    int res = 0;
    for (int i = 0; i < 1 << 24; i++)
        res ^= (n - f[i]) * (n - f[i]);
    write(res);
    return 0;
}