DDOSvoid's Blog

CF 449D Jzzhu and Numbers

发表于 分类于
本文字数： 977 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/449/D

Solution

我们考虑求出这个东西 $a[S]$ 表示值为 $S$ 的超集的数的个数

这个显然可以用高维前缀和 $O(n2^n)$ 求出来

然后我们根据 $1$ 的数量进行组合容斥即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#define maxn 20
#define ll long long 
using namespace std;

const int p = 1000000007;
const int N = 20;
const int M = (1 << N) - 1;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1) {
        if (n & 1) s = s * x % p;
        x = x * x % p;
    }
    return s;
} 

int n, m;

int a[1 << maxn];

int f[maxn]; 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr); 

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        ++a[x];
    }
    for (int o = 0; o < N; ++o)
        for (int S = M; ~S; --S)
            if (!(S >> o & 1)) a[S] += a[S | 1 << o];
    for (int S = 0; S <= M; ++S) {
        int s = 0; 
        for (int o = 0; o < N; ++o) s += S >> o & 1;
        f[s] = (f[s] + pow_mod(2, a[S]) - 1) % p;
    } int ans = 0; 
    for (int i = 0, t = 1; i < N; ++i, t = -t) ans = (ans + t * f[i]) % p;
    cout << (ans + p) % p << "\n"; 
    return 0;
}