[CF449D] Jzzhu and Numbers

[CF449D] Jzzhu and Numbers - 高维前缀和,容斥

Description

从 ({a_i}) 里面选出一个非空子集使这些数按位与起来为 0，有多少种方案

Solution

容斥，恰好有 0 个 1 的数目 = 至少有 0 个 1 的数目 - 至少有 1 个 1 的数目 + ……

设 gi 表示选择一个子集与起来，使得 i 为 1 的位上都是 1 的方案数

设 fi 表示有多少个数，满足 i 为 1 的位上都是 1，则 gi=pow(2,fi)-1

求 fi 利用高维前缀和即可

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

#define int long long
const int N = (1 << 20);
const int M = 20;
const int mod = 1e9 + 7;

int p[N], f[N], g[N], n, m;

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        f[x]++;
    }
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * 2 % mod;
    }
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if ((j & (1 << i)) == 0 && (j | (1 << i)) < N)
                f[j] += f[j | (1 << i)];
        }
    }
    for (int i = 0; i < N; i++)
    {
        g[i] = (p[f[i]] - 1 + mod) % mod;
    }
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        int t = __builtin_popcount(i);
        t = t % 2 == 1 ? -1 : 1;
        ans += t * g[i];
        ans %= mod;
        ans += mod;
        ans %= mod;
    }
    cout << ans << endl;
}