题目链接

https://codeforces.com/contest/165/problem/E

题意

给定 $n$ 个数 $a_1,a_2,…,a_n$，对于每一个 $a_i$，找出是否存在 $a_j$ 使得 $a_i$ & $a_j = 0$？

其中 $1 \leq n \leq 10^6, 1 \leq a_i \leq 4\times10^6$

题解

结论1：如果 $a_i$ & $a_j = 0$，则对于 $a_j$ 的任何一个子集 $b$（$b \subset a_j$），都有 $a_i$ & $b = 0$

结论2：$\forall i, ~a_i$ & $($~$a_i) = 0$

由上，对于每一个 $a_i$，我们都知道 ~$a_i$ 必然满足条件。所以只要找是否存在 $a_j$ 使得 $a_j \subset$ ~$a_i$ 即可。

换而言之，我们可以从高往低进行 dp，从每一个 ~$a_i$ 开始，枚举 ~$a_i$ 的子集，将满足条件的信息传递到子集中，最后看是否存在 $a_j$ 被传递了即可。

然而直接枚举子集复杂度太高，我们可以考虑按照 位数 进行dp：

我们从 $111…111$ 开始枚举，然后枚举少一个 $1$ 的情况：即 $011…11, 101…11, 110…11$ 等等。然后继续往下传递即可。

状态转移方程：

令 dp[mask] 为：这个mask是否存在 $a_j$ 使得 $mask$ & $a_j = 0$，如果存在，就是 $a_j$ 的值，否则为 $-1$

转移过程就是上述的，枚举 少一个 $1$ 的子集过程。

• 实现代码中，是从 多一个 $1$ 转移过来的，本质相同。

代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;
const int maxm = (1<<22);  // 1<<22 == 4.1e6
 
int n;
int arr[maxn];
int dp[maxm];
 
int INF = (1<<22) - 1;  // 注意INF > 4e6，我们要根据 位数 取INF，而不是根据数据范围
 
int inv(int x) {
    return (~x) & INF;  // 注意这里有 & INF 的操作，否则会得到负数
}
 
int main() { 
    fill(dp, dp+maxm, -1);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i], dp[inv(arr[i])] = arr[i];
 
    for (int mask = INF; mask >= 1; mask--) {  // 注意从 INF开始，而不是从 4e6开始，因为 inv(arr[i]) 有可能 > 4e6
        if (dp[mask] != -1) continue;
        for (int j = 0; j < 22; j++) {  
            int a = mask | (1<<j);  // 枚举多一位
            if (a == mask) continue;
            if (dp[a] != -1) {
                dp[mask] = dp[a];
                break;
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        int a = arr[i];
        cout << dp[a] << " ";
    }
    cout << endl;
}

高维前缀和

本题似乎与高维前缀和有关，这里介绍一下高维前缀和的知识。

高维前缀和主要用于解决 $dp[S] = \sum\limits_{T \subset S}a[T]$ 的问题。

在我们求一个多维度的前缀和时，有两种方法：（以下，使用求一个矩阵的前缀和来举例）

法一：枚举dp数组位置 + 容斥： $O(n2^d)$

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];

法二：枚举维度，不用容斥： $O(nd)$

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) a[i][j] += a[i][j - 1];

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) a[i][j] += a[i - 1][j];

高维前缀和的思想在于枚举每一个维度，然后让这个维度减 $1$，做前缀和。

• 如上，先枚举了第一维，然后枚举第二维。

在实现的时候就是根据维度来dp。

如果有更多维度的话，也是枚举每一个维度，然后求每个维度的前缀和：

for (int i = 0; i < d; i++) {  // 枚举每一个维度
    for (int mask = 0; mask < (1<<d); mask++) {  //求前缀和
        if (mask & (1<<i)) dp[mask] += dp[mask ^ (1<<i)];
    }
}