二进制或序列

二进制或序列

题意

给出长度为 \(n\) 的序列，任意两个数进行或运算后加入序列。

问进行无数次操作后，序列去重后的长度。

思路

定义 \(f_i\) 表示数 \(i\) 可以被序列中的元素或出的值。

若 \(f_i=i\) 表示 \(i\) 可以被序列中的元素或出来，答案加一。

从小到大枚举每个 \(i\)，将 \(f_{i \text{ or } 2^j} \gets f_{i \text{ or }2^j} \text{ or } f_i\)。

因为若 \(i\) 能被或出 \(f_i\)，\(i \text{ or } 2^j\) 也能被或出 \(f_i\)。

时间复杂度：\(O(w \log w)\)。

代码

#include <bits/stdc++.h>
using namespace std;
int f[1 << 20], n, ans;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int a; cin >> a;
        f[a] = a;
    }
    for (int i = 1; i < (1 << 20); i ++) {
        if (f[i] == i) ans ++;
        for (int j = 0; j < 20; j ++) f[i | (1 << j)] |= f[i];
    }
    cout << ans << "\n";
    return 0;
}