lessons/参考实现/03-Bitset/CodeForces-986C.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    int size = 1 << n;
    int full = size - 1;
    vector<char> present(size, false), seen_value(size, false), seen_mask(size, false);
    vector<int> values(m);
    for (int &x : values) {
        cin >> x;
        present[x] = true;
    }

    auto explore_component = [&](int source) {
        vector<pair<int, int>> stack;
        seen_value[source] = true;
        stack.push_back({source, 0});  // type 0: real value, type 1: submask state
        while (!stack.empty()) {
            auto [x, type] = stack.back();
            stack.pop_back();
            if (type == 0) {
                int mask = full ^ x;
                if (!seen_mask[mask]) {
                    seen_mask[mask] = true;
                    stack.push_back({mask, 1});
                }
            } else {
                if (present[x] && !seen_value[x]) {
                    seen_value[x] = true;
                    stack.push_back({x, 0});
                }
                for (int bits = x; bits != 0; bits &= bits - 1) {
                    int bit = bits & -bits;
                    int next = x ^ bit;
                    if (!seen_mask[next]) {
                        seen_mask[next] = true;
                        stack.push_back({next, 1});
                    }
                }
            }
        }
    };

    int components = 0;
    for (int x : values) {
        if (!seen_value[x]) {
            ++components;
            explore_component(x);
        }
    }
    cout << components << '\n';
    return 0;
}