等或划分

形式化题目

给定 $n$ 个非负整数 $a_i$ ，每个元素独立放入集合 $A$ 或 $B$ （共 $2^n$ 种划分，空集合的或为 $0$ ）。求满足 $OR(A) = OR(B)$ 的划分方案数，模 $998244353$ 。

思路

一句话本质：把条件拆到二进制位上，合法划分 ⟺ 全或 $T$ 的每一位，其"第 $k$ 位为 1 的数"在 $A$ 、 $B$ 中都有出现；正着统计"每一位都被劈开"会重叠，改用容斥数"至少有一位没劈开"的坏事件，坏事件的交集用并查集（强制同侧）压缩成 $2^{连通块数}$ ，答案就是 $\sum_{S \subseteq T} (-1)^{|S|} \cdot 2^{cc(S)}$ 。

先看一个可以直接验证想法的朴素解：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 21:26
 * update_at: 2026-08-28 21:26
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
// choose[i] = 0/1 表示第 i 个数放入 A / B 集合，枚举完整的 choose[1..n]
// 后到叶子节点统一检查 OR(A) 是否等于 OR(B)。只适合 n <= 20 的小数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
int a[MAXN];
int choose[MAXN]; // choose[i] = 0 表示第 i 个数分给 A，1 表示分给 B
long long ans;

// 检查当前完整的 choose[1..n] 是否合法：OR(A) == OR(B)
bool check() {
    int orA = 0, orB = 0;
    for (int i = 1; i <= n; i++) {
        if (choose[i] == 0) orA |= a[i];
        else orB |= a[i];
    }
    return orA == orB;
}

// 枚举第 dep 个数的去向（选择序列），生成完整序列后在叶子统一检查
void dfs(int dep) {
    if (dep == n + 1) {
        if (check()) ans++; // 合法方案数加 1
        return;
    }
    for (int c = 0; c <= 1; c++) {
        choose[dep] = c;
        dfs(dep + 1);
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    dfs(1);
    cout << ans % 998244353 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

这个暴力把问题看成一串 01 选择：choose[i] = 0/1 表示第 $i$ 个数放入 $A$ / $B$ 集合。递归先生成完整的 choose[]，到叶子节点再统一计算 $OR(A)$ 、 $OR(B)$ 并判断是否相等。它枚举了全部 $2^n$ 种划分，只适合 $n \leqslant 20$ 的小数据。

问题？ 直接枚举所有划分，瓶颈在哪里？

$2^n$ 对 $n = 200$ 完全不可行。但值域只有 15 个二进制位，提示我们应该从"位"而不是从"划分"入手：把合法性条件按位拆开。

问题？ 一个合法划分，对每一位 $k$ 有什么要求？

设 $T = a_1 \mid a_2 \mid \cdots \mid a_n$ 为全体或。任何划分都有 $OR(A) \mid OR(B) = T$ ；若 $OR(A) = OR(B) = X$ ，则 $X \mid X = X = T$ ，所以两边都必须等于 $T$ 。于是对 $T$ 中的每一位 $k$ ， $A$ 和 $B$ 里都必须各有一个第 $k$ 位为 1 的数——第 $k$ 位的"1-数集合"必须被劈成两半，两边都有。

问题？ 反过来，每一位的 1-数都被劈开，就一定合法吗？

是。若 $T$ 的每一位在 $A$ 、 $B$ 中都出现，则 $OR(A)$ 、 $OR(B)$ 都含 $T$ 的全部位、也不含 $T$ 之外的位，所以都等于 $T$ 。因此：

合法划分 ⟺ 对每个 $k \in T$ ，第 $k$ 位为 1 的数不能全部落在同一个集合。

问题？ 正着统计"每一位都被劈开"，难在哪里？

一个元素（如 $7$ ）可以同时是多个位的 1-数，它去哪边会同时影响所有相关位；"两个位的 1-数都劈开"的计数互相纠缠，没法直接相乘。正难则反：数"至少有一位没被劈开"的划分。

问题？ 坏事件怎么描述，容斥怎么展开？

定义坏事件 $E_k$ = “第 $k$ 位的 1-数全部落在同一个集合”。合法方案 = 总数 − 坏事件并集，用容斥原理展开：

\text{ans} = \sum_{S \subseteq T} (-1)^{|S|} \cdot \Big| \bigcap_{k \in S} E_k \Big|

$S = \varnothing$ 时该项就是总数 $2^n$ 。

问题？ 交集 $\bigcap_{k \in S} E_k$ ——“S 中每一位的 1-数都同侧”，怎么数？

这是本题的第二个关键卡点：约束"同侧"是等价关系。同一位的 1-数互相绑定；两个位共享元素时，绑定关系还要传递下去——这正是并查集。对每个 $k \in S$ ，把第 $k$ 位为 1 的所有元素 union 到一起，结束后得到 $cc$ 个连通块。

问题？ 为什么每个连通块恰好有 2 种选择、且互不干扰？

强制条件只约束"同侧"，从不指定"哪侧"：每个连通块全放 $A$ 或全放 $B$ 都满足所有强制；不同连通块之间没有共享元素、没有共享约束，用乘法原理相乘。所以 $\big| \bigcap_{k \in S} E_k \big| = 2^{cc(S)}$ 。

问题？ 枚举量能承受吗？

$S$ 只取 $T$ 的子集， $T < 2^{15}$ ，最多 $2^{15}$ 种；每种先 $O(n)$ 初始化并查集，再对 $S$ 中每个位做合并，总操作 $O(2^{15} \cdot 16n) \approx 10^8$ ，可行。

用样例 1 验证公式（ $a = 4,5,6,7$ ，即 $100,101,110,111$ ， $T = 7$ ）。下表列出全部 8 个 $S \subseteq T$ 的合并情况与贡献：

| $S \subseteq T$ | 并查集合并的 1-数 | $cc$ | $(-1)^{|S|} \cdot 2^{cc}$ | | — | — | — | — | | $\varnothing$ | 无 | 4 | $+16$ | | $\{位0\}$ | $5,7$ | 3 | $-8$ | | $\{位1\}$ | $6,7$ | 3 | $-8$ | | $\{位2\}$ | $4,5,6,7$ | 1 | $-2$ | | $\{位0,位1\}$ | $\{5,7\} \cup \{6,7\} \to 5,6,7$ | 2 | $+4$ | | $\{位0,位2\}$ | 全部 | 1 | $+2$ | | $\{位1,位2\}$ | 全部 | 1 | $+2$ | | $\{位0,位1,位2\}$ | 全部 | 1 | $-2$ |

行表示当前枚举的强制位集合 $S$ ， $cc$ 是合并后的连通块数，最后一列是该子集对答案的贡献。合计 $16-8-8-2+4+2+2-2 = 4$ ，正好等于样例答案；例如 $S = \{位0,位1\}$ 时， $5,6,7$ 三数因共享位 0/位 1 被绑成一个块，块内必须同侧，块外只有 $4$ 独立，共 $2^2 = 4$ 种分配。

实现要点：预先对每个位 $k$ 存好 1-数下标列表（bitList[k]），避免每次扫描全数组；用 __builtin_popcount(S) 的奇偶性定符号；减法取模先加模数。

代码

cpp

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
79
80
81
82
83
84
85
86
87
88
89/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 21:26
 * update_at: 2026-08-28 21:26
 */
// main.cpp：容斥 + 并查集。
// 枚举 T 的子集 S（2^15 种），对 S 中每一位 k，把所有第 k 位为 1 的数用并查集合并（强制同组），
// 每个连通块有 2 种去向（A 或 B），贡献 (-1)^{|S|} * 2^{连通块数}，求和即答案。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;   // n 的上界
const int MAXB = 15;    // 位数：0 <= a_i < 2^15
const int MOD = 998244353;

int n;
int a[MAXN];

// bitList[k][0..bitLen[k]-1]：第 k 位为 1 的所有元素下标
int bitList[MAXB][MAXN];
int bitLen[MAXB];

int father[MAXN];       // 并查集父节点
long long pow2[MAXN];   // pow2[c] = 2^c % MOD

// 并查集：找根（带路径压缩）
int find(int u) {
    if (father[u] == u) return u;
    return father[u] = find(father[u]);
}

void solve() {
    // T = 全部元素的或；只可能出现在 T 中的位才需要被“检查”
    int T = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        T |= a[i];
    }

    // 预处理：每一位的 1-数列表，省去后面每次重复扫描
    for (int k = 0; k < MAXB; k++)
        for (int i = 1; i <= n; i++)
            if (a[i] & (1 << k))
                bitList[k][bitLen[k]++] = i;

    pow2[0] = 1;
    for (int i = 1; i <= n; i++)
        pow2[i] = pow2[i - 1] * 2 % MOD;

    long long ans = 0;
    // 容斥：枚举 T 的子集 S，S 中每一位都被“强制”：该位为 1 的数同处一个集合
    for (int S = 0; S < (1 << MAXB); S++) {
        if ((T & S) != S) continue; // 只枚举 T 的子集

        for (int i = 1; i <= n; i++) father[i] = i; // 初始化并查集

        // 对 S 中每一位 k，把第 k 位为 1 的所有数合并成一个连通块
        for (int k = 0; k < MAXB; k++) {
            if (!(S & (1 << k))) continue;
            for (int i = 1; i < bitLen[k]; i++) {
                int u = find(bitList[k][0]);
                int v = find(bitList[k][i]);
                if (u != v) father[u] = v;
            }
        }

        // 统计连通块个数：每个块独立选择 A 或 B，共 2^cc 种
        int cc = 0;
        for (int i = 1; i <= n; i++)
            if (find(i) == i) cc++;

        if (__builtin_popcount(S) & 1)
            ans = (ans - pow2[cc] + MOD) % MOD; // 奇数个强制位取负号
        else
            ans = (ans + pow2[cc]) % MOD;
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

复杂度

时间：枚举 $2^{15}$ 个子集，每个子集 $O(n + \sum \text{popcount}(a_i)) \leqslant O(16n)$ ，总 $O(2^{15} \cdot 16n)$ ， $n = 200$ 时约 $10^8$ 次操作。
空间： $O(15n)$ （每位 1-数列表） $+ O(n)$ （并查集、幂表）。

总结

核心转化一（等价）： $OR(A) = OR(B) \iff$ 全或 $T$ 的每一位，其 1-数在两边都有出现。注意这里隐含了"两边都等于 $T$ "。
核心转化二（正难则反 + 容斥）："每一位都劈开"重叠难数，改数坏事件 $E_k$ = "第 $k$ 位 1-数全在同侧"的并集，答案 $= \sum_{S \subseteq T} (-1)^{|S|} \cdot 2^{cc(S)}$ 。
核心转化三（等价关系 → 并查集）："同侧"是传递的，把 $k \in S$ 的 1-数 union 后，每个连通块独立选 $A/B$ ，交集大小 $= 2^{cc(S)}$ 。
可迁移思想：计数题里"每个对象都必须如何"若重叠，先写坏事件再做容斥；"必须同组/同侧"一类约束优先想到并查集的传递闭包，而不是枚举分组。

图示解析

这张 ASCII 图展示"位分解 → 等价 → 容斥 → 并查集 → 答案"的解法路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
162^n 种划分（暴力枚举，只适合 n ≤ 20）
        │  条件按位拆开
        ▼
合法 ⟺ T 的每一位，其 1-数在 A、B 中都出现（两边或都等于 T）
        │  正难则反：坏事件 E_k = 第 k 位 1-数全在同侧
        ▼
容斥：ans = Σ_{S⊆T} (−1)^{|S|} · |∩_{k∈S} E_k|
        │  "同侧"是等价关系，传递合并
        ▼
并查集：对每个 k ∈ S，把第 k 位的 1-数 union → cc 个连通块
        │  每块独立选 A 或 B（乘法原理）
        ▼
|∩_{k∈S} E_k| = 2^cc ；枚举 S ⊆ T 共 ≤ 2^15 种
        │
        ▼
答案 = Σ (−1)^{|S|} · 2^{cc(S)} mod 998244353

从下往上看：等价引理把"划分合法"变成"每位都被劈开"；容斥把重叠的正面计数换成坏事件交集的求和；并查集把"强制同侧"压缩成连通块并给出闭式 $2^{cc}$ 。三个转化缺一不可，每层都对应一个独立的计数困难。

目录

形式化题目

思路

代码

复杂度

总结

图示解析