CodeChef - COVERING 高维前后缀和 + 容斥原理

题意

传送门 CodeChef Covering Sets

题解

令 $$T(S)=\sum _{(A\cup B\cup C)=S}F(A)G(B)H(C)$$ 二进制状态压缩表示 $S$，则 $R(S)$ 是关于 $T(S)$ 的高维后缀和，即 $$R(S)=\sum _{S\in A}T(A)$$ 问题转换为如何求解 $T(S)$。考虑每一个元素是否存在，即二进制表示下每一位是否为零，可以应用容斥原理得到（方便起见，之后的 $F,G,H$ 表示其高维前缀和） $$T(S)=\sum _{A\in S}(-1{)}^{|S\setminus A|}F(A)G(A)H(A)$$ 朴素地枚举子集的子集 $O(n{3}^n)$ 显然难以胜任。需要对多个子集应用容斥原理时，可以考虑使用高维前缀和进行优化。令 $D(S)=F(S)G(S)H(S)$，考虑它对各个子集的贡献。由于集合规模的奇偶性不同，$D(S)$ 的贡献的奇偶性也不同，不妨令 $|S|$ 为奇数是取负；对 $D(S)$ 计算高维前缀和后，再对 $|S|$ 为奇数的项取负即可得到 $T(S)$。

总时间复杂度 $O(n{2}^n)$。

#include 
using namespace std;
constexpr int MOD = (int)1e9 + 7;
using ll = long long;

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

    int n;
    cin >> n;

    auto add = [&](int &x, int y) {
        x += y;
        if (x >= MOD) x -= MOD;
    };

    vector<int> a(1 << n), b(1 << n), c(1 << n);
    for (int i = 0; i < 1 << n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < 1 << n; ++i) {
        cin >> b[i];
    }
    for (int i = 0; i < 1 << n; ++i) {
        cin >> c[i];
    }

    auto get = [&](vector<int> &a) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                if (j >> i & 1) {
                    add(a[j], a[j ^ 1 << i]);
                }
            }
        }
    };
    get(a);
    get(b);
    get(c);

    vector<int> g(1 << n), coef(1 << n);
    for (int i = 0; i < 1 << n; ++i) {
        g[i] = (ll)a[i] * b[i] % MOD * c[i] % MOD;
        int c = 0;
        for (int j = 0; j < n; ++j) {
            if (i >> j & 1) {
                ++c;
            }
        }
        coef[i] = c & 1;
        if (coef[i] > 0) {
            g[i] = MOD - g[i];
        }
    }
    get(g);
    for (int i = 0; i < 1 << n; ++i) {
        if (coef[i] > 0) {
            g[i] = MOD - g[i];
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 1 << n; ++j) {
            if (!(j >> i & 1)) {
                add(g[j], g[j ^ 1 << i]);
            }
        }
    }

    int res = 0;
    for (int i = 0; i < 1 << n; ++i) {
        add(res, g[i]);
    }
    cout << res << '\n';

    return 0;
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78