1 条题解

  • 0
    @ 2026-11-15 22:53:18

    60pts

    首先可以把所有元素都进行与运算,得到一个结果 cc,把所有集合内的元素和 cc 进行异或运算,这样答案不变,使得所有元素与运算的结果为 00。

    接下来用 f[i]f[i],表示所有包含 2i2^i 这一位的集合 SS 内的所有数与运算的结果,可以发现,答案一定是 f[0],f[1],…,f[39]f[0],f[1],…,f[39]​ 每个数取或不取,或运算得到的结果去重。

    进一步转化,问题等价于如果对于一对 x,yx,y,满足 f[x]f[x] 中所有 11 被 f[y]f[y] 包含,那么 x,yx,y​ 不能同时选,问方案数。

    问题等价于给定一个 4040​ 个点的图,有连边的点不能同时选,问选择的方案数。

    当 3030 个点时,如果一个点是孤立点,那么直接忽略,把答案乘 22,否则任取一个点选或不选,如果不选变成 n−1n-1 的子问题,如果选至少有额外一个点不能选,变成至少 n−2n-2 的子问题,复杂度为 f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2),为斐波那契的第 3030 项,数据没有卡的特别慢,这种做法在常数优秀的情况下也能通过 100100 分。

    100pts

    考虑枚举前 2020 个点选或不选,就能知道剩下 2020 个点是否可以选。

    我们先预处理出后 2020 个点 2202^{20} 种情况做判定,利用高维前缀和算出所有可能情况的答案,然后利用meet in the middle,枚举前 2020 个点的情况,直接计算即可。

    复杂度为 220×202^{20} \times 20。

    #include<bits/stdc++.h> 
    
    using namespace std;
    
    const int K = 40;
    
    const int KEK = 1 << 23;
    
    long long memo[KEK + 228];
    
    long long calc_dp(long long mask, vector<long long>& inside) {
        if (mask < KEK && memo[mask]) {
            return memo[mask];
        }
        int mx_bit = 63 - __builtin_clzll(mask);
        long long ans = calc_dp((mask ^ (1ll << mx_bit)) & (~inside[mx_bit]), inside) + 
        calc_dp(mask ^ (1ll << mx_bit), inside);
        if (mask < KEK)
            memo[mask] = ans;
        return ans;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        
    
    
        int n;
        cin >> n;
        vector<long long> A(n);
        for (int i = 0; i < n; ++i)
            cin >> A[i];
        long long total_and = (1ll << K) - 1;
        for (int i = 0; i < n; ++i)
            total_and &= A[i];
        for (int i = 0; i < n; ++i)
            A[i] ^= total_and;
        vector<long long> ands(K);
        for (long long x : A) {
            for (int i = 0; i < K; ++i) {
                if (x & (1ll << i)) {
                    if (ands[i] != 0)
                        ands[i] &= x;
                    else
                        ands[i] = x;
                }
            }
        }
        vector<long long> vals;
        for (int i = 0; i < K; ++i) {
            if (ands[i])
                vals.emplace_back(ands[i]);
        }
        sort(vals.begin(), vals.end());
        vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
        int m = vals.size();
        vector<long long> inside(m);
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                if ((vals[i] & vals[j]) == vals[i])
                    inside[j] |= 1ll << i;
            }
        }
        memo[0] = 1;
        cout << calc_dp((1ll << m) - 1, inside) << '\n';
        return 0;
    }
    
    
    • 1

    信息

    ID
    226
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者