题目链接

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];

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

• 这种方法的复杂度远低于法一!


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

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)];
    }
}