CF165E Compatible Numbers

LuoGu: CF165E Compatible Numbers

CF: E. Compatible Numbers

a & b = 0 等价于将 $a$ 取反后 $b \subseteq a$ ，对于每一个数考察是否子集中有数，考虑高维前缀和，任选一个即可。

查看代码

#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 << 22;
int n, w[N], f[N];
int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
    {
        read(w[i]);
        f[w[i]] = w[i];
    }
    for (int i = 0; i < 22; i++)
        for (int j = 0; j < 1 << 22; j++)
            j >> i & 1 && !f[j] && (f[j] = f[j ^ 1 << i]);
    for (int i = 1; i <= n; i++)
    {
        int t = (1 << 22) - 1 ^ w[i];
        write(f[t] ? f[t] : -1), putchar(' ');
    }
    return 0;
}