Jzzhu and Numbers

第一层：容斥原理的引入
第一层的解释: 容斥原理的两种视角
举例子
第二层：将转化为元素计数
第二层的解释: 从子序列到元素的转换
第三层：SOS DP 计算超集和
1. 状态转移逻辑推导：
完整算法流程
为什么这道题很“高级”？
信号反射

这道题是 SOS DP 结合 容斥原理 (Inclusion-Exclusion Principle) 的巅峰之作。要解析这道题，我们需要从“恰好为 0”这个难点出发，一步步推导到“超集求和”。

既然你已经掌握了子集 SOS DP 的逻辑，我们来看这道题的三个推导层次。

第一层：容斥原理的引入

我们要找的是子序列 AND 结果恰好为 $0$ 。在位运算中，“恰好为 0”意味着：

第 $0$ 位不能全是 $1$ 。
第 $1$ 位不能全是 $1$ 。
…
第 $19$ 位不能全是 $1$ 。

根据容斥原理，我们要计算满足“没有任何位全是 1”的方案数：

Ans = \sum_{mask \subseteq U} (-1)^{|mask|} \cdot g(mask)

其中：

$|mask|$ 是 $mask$ 中二进制 $1$ 的个数。
$g(mask)$ 是满足“至少 $mask$ 指定的那些位全为 1”的子序列方案数。

注意： $g(mask)$ 并不要求其他位是 $0$ 还是 $1$ ，它只保证 $mask$ 覆盖的那些位在 AND 结果中一定是 $1$ 。

第一层的解释: 容斥原理的两种视角

理解容斥原理（Principle of Inclusion-Exclusion, PIE）是进阶组合数学和位运算 DP 的分水岭。既然你熟悉离散数学，我们直接用形式化的语言，从两个视角把这个“恰好为 0”的问题拆解清楚。

我们的目标是：求按位与结果没有任何一位全是 1 的子序列方案数。

1. 集合论视角：补集的交集

设 $U$ 为所有可能的非空子序列构成的全集。

对于每一位 $j \in \{0, 1, \dots, 19\}$ ，我们定义一个集合 $S_j$ ：

$S_j = \{ \text{所有满足“第 } j \text{ 位全是 1”的子序列} \}$

我们要找的是：既不在 $S_0$ 中，也不在 $S_1$ 中……直到不在 $S_{19}$ 中的子序列。

即计算补集的交集：

|\overline{S_0} \cap \overline{S_1} \cap \dots \cap \overline{S_{19}}|

根据德·摩根定律，这等价于：

|U| - |S_0 \cup S_1 \cup \dots \cup S_{19}|

根据容斥原理的标准公式，并集的模等于：

|S_0 \cup S_1 \cup \dots \cup S_{19}| = \sum |S_i| - \sum |S_i \cap S_j| + \sum |S_i \cap S_j \cap S_k| - \dots

将此代入 $|U| - \text{并集}$ ，我们得到：

Ans = \sum_{mask \subseteq \{0,\dots,19\}} (-1)^{|mask|} \cdot | \bigcap_{j \in mask} S_j |

关键推导：

$| \bigcap_{j \in mask} S_j |$ 的含义是：子序列在 $mask$ 所指定的那些位上全都是 1。

这正对应了我们之前定义的 $g(mask)$ ：

$g(mask)$ 表示“至少 $mask$ 这些位全是 1”的方案数。
$|mask|$ （即 $popcount$ ）决定了该项前面的正负号。

2. 命题逻辑视角：属性的否定

设属性 $P_j$ 表示：“子序列在第 $j$ 位全是 1”。

我们需要计算满足 $\neg P_0 \land \neg P_1 \land \dots \land \neg P_{19}$ 的情况总数。

利用逻辑等价式：

\bigwedge_{j=0}^{19} \neg P_j \equiv \neg \left( \bigvee_{j=0}^{19} P_j \right)

在逻辑计数中，如果我们想求“没有任何属性成立”的情况，可以使用**指示函数（Characteristic Function）**的恒等式：

\prod_{j=0}^{19} (1 - \mathbb{I}(P_j))

其中 $\mathbb{I}(P_j)$ 在属性 $P_j$ 成立时为 1，否则为 0。

将这个乘积式展开：

(1 - \mathbb{I}(P_0))(1 - \mathbb{I}(P_1))\dots(1 - \mathbb{I}(P_{19})) = 1 - \sum \mathbb{I}(P_i) + \sum \mathbb{I}(P_i \land P_j) - \dots

对所有子序列求和（即求期望值的和）：

\sum_{\text{subsequences}} \left( \sum_{mask} (-1)^{|mask|} \mathbb{I}(\text{属性 } mask \text{ 中的位全是 1}) \right)

交换求和次序（这是组合数学中极常用的技巧）：

\sum_{mask} (-1)^{|mask|} \left( \sum_{\text{subsequences}} \mathbb{I}(\text{属性 } mask \text{ 中的位全是 1}) \right)

括号内部的部分 $\sum_{\text{subsequences}} \mathbb{I}(\dots)$ 正好就是 $g(mask)$ 。

3. 总结与对照表

通过这两种推导，我们可以建立一个直观的联系：

维度	逻辑/集合语言	SOS DP 中的具体含义
全集 $U$	所有非空子序列	$mask = 0$ 时的 $g(0)$ ，即 $2^n-1$
属性 $P_j$	第 $j$ 位全是 1	子序列中每个元素都是 $2^j$ 的超集
交集 $\bigcap S_j$	多位同时全是 1	子序列中每个元素都是 $mask$ 的超集
**容斥系数 $(-1)^{	mask	}$**

代码段

graph TD
    A["恰好结果为 0"] -- "逻辑否定" --> B["没有任何位全是 1"]
    B -- "容斥展开" --> C["计算: 至少某些位全是 1"]
    C -- "转化" --> D["计算: 每个元素都是 mask 的超集"]
    D -- "SOS DP" --> E["高效求出 f(mask)"]
    E -- "组合计数" --> F["g(mask) = 2^f(mask) - 1"]
    F -- "求和" --> G["最终答案"]

为什么这一步必须用 SOS DP？

因为在容斥公式中，我们需要对每一个 $mask$ （共 $2^{20}$ 个）求出 $g(mask)$ 。而要求 $g(mask)$ ，首先得知道数组中有多少个数是 $mask$ 的超集。

如果对每个 $mask$ 暴力遍历数组， $O(2^N \cdot n)$ ，必 TLE。
利用 SOS DP，我们可以用 $O(N \cdot 2^N)$ 的时间预处理出所有 $mask$ 的超集计数。

你想现在尝试把这个容斥逻辑写成 C++ 代码吗？或者需要我解释一下为什么 $g(mask) = 2^{f(mask)} - 1$ 而不是直接用 $f(mask)$ ？

举例子

如果 $n=3$ ，且这三个数字分别是 $a_1=0, a_2=1, a_3=2$ ，那么全集 $U$ 指的是所有可能的下标组合（即非空子集）。

在组合数学中，全集 $U$ 的大小由 $2^n - 1$ 决定。对于 $n=3$ ，总共有 $7$ 个非空子序列。

$U$ 的具体构成

我们可以通过枚举下标来列出 $U$ 中的每一个元素（每一个元素都是原序列的一个子集）：

编号	下标组合	对应数值	按位与 (AND) 结果	是否符合 “AND=0”
1	$\{1\}$	$\{0\}$	$0$	是
2	$\{2\}$	$\{1\}$	$1$	否
3	$\{3\}$	$\{2\}$	$2$	否
4	$\{1, 2\}$	$\{0, 1\}$	$0 \ \& \ 1 = 0$	是
5	$\{1, 3\}$	$\{0, 2\}$	$0 \ \& \ 2 = 0$	是
6	$\{2, 3\}$	$\{1, 2\}$	$1 \ \& \ 2 = 0$	是
7	$\{1, 2, 3\}$	$\{0, 1, 2\}$	$0 \ \& \ 1 \ \& \ 2 = 0$	是

关键点解析

全集 $U$ 的本质： $U$ 并不是一个包含数字的集合，而是一个包含集合的集合（A set of sets）。它的每个元素都是从原数组中挑选出来的一种“成组方案”。
计数意义：
- 在 Jzzhu and Numbers 这道题中，目标就是找出 $U$ 中有多少个元素的“按位与结果”等于 $0$ 。
- 在这个例子中，答案就是 5。
区分数值与下标：即便两个数字的值相同（比如数组是 [0, 0, 0]），挑选“第一个 0”和挑选“第二个 0”被视为不同的方案，对应 $U$ 中不同的子序列。

容斥原理在这里怎么运作？

在这一层推导中，我们不会去一个一个检查这 7 个方案，而是利用属性来剔除：

属性 $P_0$ ：子序列 AND 结果的第 0 位是 1（方案 2 是其中之一）。
属性 $P_1$ ：子序列 AND 结果的第 1 位是 1（方案 3 是其中之一）。
我们要的是：既不满足 $P_0$ 也不满足 $P_1$ 的方案。

通过容斥公式：

Ans = (\text{所有方案}) - (\text{满足 } P_0 \text{ 的方案}) - (\text{满足 } P_1 \text{ 的方案}) + (\text{同时满足 } P_0, P_1 \text{ 的方案})

你会发现，SOS DP 正是用来快速算出“满足 $P_0, P_1 \dots$ ”这些属性的方案数的。

第二层：将 $g(mask)$ 转化为元素计数 $f(mask)$

如何求 $g(mask)$ ？

一个子序列的 AND 结果在 $mask$ 的位上全为 $1$ ，当且仅当该子序列中的每一个数在 $mask$ 的位上都全为 $1$ 。
用集合语言描述：子序列中的每个元素 $a_i$ 必须满足 $mask \subseteq a_i$ （即 $a_i$ 是 $mask$ 的超集）。
假设在给定的 $n$ 个数中，有 $f(mask)$ 个数是 $mask$ 的超集。
那么，从这 $f(mask)$ 个数中任意挑选元素组成非空子序列，它们的 AND 结果一定包含 $mask$ 。

$g(mask) = 2^{f(mask)} - 1$
(题目允许 $k \geqslant 1$ ，所以是 $2^{f(mask)}-1$ ；如果不要求非空则是 $2^{f(mask)}$ ，最后对结果统一处理。)

第二层的解释: 从子序列到元素的转换

这一层的核心是理解子序列的性质如何转化为元素的性质。我们需要将“子序列的 AND 结果”转化为“元素的超集关系”。

g(mask) 转化为元素计数 f(mask)
第二层 $g(mask) = 2^{f(mask)} - 1$ 这个公式怎么得到?

要推导这个公式，我们需要利用离散数学中的两个核心概念：集合交集的性质 和 幂集（Power Set）的计数定理。

我们将这个过程分为三个严谨的逻辑步骤。

第一步：位运算与集合论的同构

在离散数学中，一个 $N$ 位的二进制数可以看作是全集 $U = \{0, 1, \dots, N-1\}$ 的一个子集。

设数字 $a$ 对应的集合为 $A = \{j \mid a \text{ 的第 } j \text{ 位是 } 1\}$ 。
设 $mask$ 对应的集合为 $M$ 。
按位与（AND）运算 对应集合的 交集（Intersection）。

因此，子序列 $\{a_{i_1}, a_{i_2}, \dots, a_{i_k}\}$ 的 AND 结果包含 $mask$ ，在集合论中表示为：

M \subseteq (A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k})

第二步：交集包含关系的等价转化

根据交集的定义： $x \in (S_1 \cap S_2 \cap \dots \cap S_k)$ 当且仅当对于所有的 $j \in \{1 \dots k\}$ ，都有 $x \in S_j$ 。

由此可以推导出一个关键的逻辑等价式：

M \subseteq \bigcap_{j=1}^{k} A_{i_j} \iff \forall j \in \{1 \dots k\}, M \subseteq A_{i_j}

推导过程：

$(\Rightarrow)$ 方向：如果 $M$ 是所有集合交集的子集，而交集本身又是其中任何一个集合 $A_{i_j}$ 的子集，根据子集关系的传递性， $M \subseteq A_{i_j}$ 对所有 $j$ 成立。
$(\Leftarrow)$ 方向：如果每一个 $A_{i_j}$ 都包含了 $M$ ，那么它们的公共部分（交集）自然也至少包含了 $M$ 。

结论：一个子序列的 AND 结果要包含 $mask$ ，前提条件是子序列里的每一个元素都必须是 $mask$ 的超集。

第三步：基于幂集的组合计数

现在我们把问题转变成一个纯粹的计数问题：

定义候选池：

在原始的 $n$ 个数中，满足“是 $mask$ 的超集”这一条件的数构成的集合为 $X_{mask}$ 。

$X_{mask} = \{ a_j \mid mask \subseteq a_j \}$
根据你的定义，这个集合的大小 $|X_{mask}| = f(mask)$ 。
构建子序列：

任何一个满足条件的子序列，其元素必须全部来自于 $X_{mask}$ 。也就是说，每一个合法的子序列都是 $X_{mask}$ 的一个子集。
计算子集总数：

根据离散数学中的幂集定理：一个大小为 $m$ 的集合，其幂集（所有子集构成的集合）的大小为 $2^m$ 。

这里 $m = f(mask)$ ，所以总共有 $2^{f(mask)}$ 种可能的子序列。
排除非法情况：

幂集中包含一个空集（即一个数字都不选的情况）。

题目要求是“非空子序列”（ $k \geqslant 1$ ），因此我们需要从总数中减去这 $1$ 种空集的情况。

最终公式：

g(mask) = 2^{f(mask)} - 1

总结

这个推导展示了为什么 $f(mask)$ 是解决问题的桥梁：

$f(mask)$ ：衡量了在“高维空间”中，有多少个点落在了 $mask$ 所在的“上方区域”（超集区域）。
$g(mask)$ ：利用指数级增长的特性，将“点的数量”转化为了“由点构成的组合数量”。

这也是为什么 SOS DP 如此强大的原因：它让我们能在 $O(N \cdot 2^N)$ 的时间内，为每一个可能的 $mask$ 都划定好这个“候选池”的大小。

第三层：SOS DP 计算超集和 $f(mask)$

现在的核心矛盾变成了：如何快速求出 $f(mask)$ ？

$f(mask)$ 定义为：有多少个 $a_i$ 满足 $(a_i \operatorname{\&} mask) = mask$ 。

这是典型的超集求和问题。在 SOS DP 中，我们只需要改变一下遍历的方向和条件：

代码段

graph LR
    A["子集和 (Subset)"] --> B["mask & (1#60;#60;i) 为真"]
    B --> C["从 mask ^ 2^i 转移到 mask"]
    D["超集和 (Superset)"] --> E["mask & (1#60;#60;i) 为假"]
    E --> F["从 mask ^ 2^i 转移到 mask"]
    
    style F fill:#f96,stroke:#333,stroke-width:2px

状态转移逻辑推导：

定义 $dp[i][mask]$ 为：考虑前 $i$ 位，满足 $a_k$ 在高位（ $>i$ ）与 $mask$ 严格一致，且在低位（ $\leqslant i$ ）是 $mask$ 的超集的元素个数。

如果 mask 的第 $i$ 位是 $1$ ：

那么 $a_k$ 的第 $i$ 位必须是 $1$ 。此时没有选择余地：

$dp[i][mask] = dp[i-1][mask]$
如果 mask 的第 $i$ 位是 $0$ ：

那么 $a_k$ 的第 $i$ 位可以是 $0$ （对应 $dp[i-1][mask]$ ），也可以是 $1$ （对应 $dp[i-1][mask \oplus 2^i]$ ）。

$dp[i][mask] = dp[i-1][mask] + dp[i-1][mask \oplus 2^i]$

完整算法流程

统计频率：用 cnt[x] 记录数组中数字 $x$ 出现的次数。

超集 SOS DP：

cpp

1
2
3
4for(int i = 0; i < 20; ++i)
    for(int mask = 0; mask < (1 << 20); ++mask)
        if (!(mask & (1 << i)))
            cnt[mask] = (cnt[mask] + cnt[mask ^ (1 << i)]) % MOD;

容斥计算：

cpp

1
2
3
4
5
6
7
8long long ans = 0;
for(int mask = 0; mask < (1 << 20); ++mask) {
    long long combinations = (pow2[cnt[mask]] - 1); // 2^f(mask) - 1
    if (__builtin_popcount(mask) % 2 == 1)
        ans = (ans - combinations + MOD) % MOD;
    else
        ans = (ans + combinations) % MOD;
}

为什么这道题很“高级”？

这道题巧妙地利用了位运算的对偶性：

题目求的是 AND（向下的操作）。
容斥原理将其转化为超集统计（向上的操作）。
SOS DP 完美解决了多维空间下的前缀和计算，将 $O(3^{20})$ 降到了 $O(20 \cdot 2^{20})$ 。

这道题你打算自己动手写一下吗？在写 pow2 预处理和处理取模时需要注意细节。如果你写好了，我们可以讨论一下这道题的变体：如果要求 OR 结果恰好为 $2^{20}-1$ 该怎么改？

信号反射

这种感觉非常正常。在 Codeforces 上，2200 分（Candidate Master 等级）及以上的题目，通常不会只考查一个孤立的知识点，而是考查知识点的复合转化。

你能通过这三个层级的推导，说明你已经具备了极强的逻辑拆解能力。比赛时想不出来，往往是因为还没建立起特定的**“信号反射”**。

如何建立“信号反射”：看到什么该想 SOS DP + 容斥？

你可以把这道题抽象成一个“思维模版”，以后看到类似特征就往这方面靠：

1. 信号一：关键词“子序列” + “位运算结果为 X”

反射：子序列意味着 $2^n$ 的组合，位运算意味着我们可以按位考虑。
直觉：这通常涉及“贡献转换”。我们不能枚举子序列，但我们可以枚举位掩码 (mask)。

2. 信号二：要求结果“恰好”是 0，或者是某个特定值

反射：在位运算中，“恰好”往往意味着“某些位必须是 0”。
直觉：使用容斥原理 (PIE)。
- “恰好为 0” $\to$ “没有任何位全为 1”。
- “恰好为 $K$ ” $\to$ “固定某些位为 1，其余位随意”再进行容斥。

3. 信号三：需要对 $2^N$ 个掩码分别计算某种“包含关系”的统计量

反射：如果暴力计算每个 mask 的超集/子集，复杂度是 $O(3^N)$ 或 $O(N \cdot 2^N)$ 。
直觉：这就是 SOS DP 的主场。它就是为了高效处理这种“高维前缀和”而生的。

你的思维进化路径

我们可以用一张图来总结你这次学习的思维升级：

代码段

graph TD
    Level1[目标: 恰好为 0] -- "思维跳跃: 容斥原理" --> Level2[中间态: 至少某些位全是 1]
    Level2 -- "思维跳跃: 组合数学" --> Level3[基础态: 统计有多少个数字是 mask 的超集]
    Level3 -- "思维跳跃: 算法优化" --> Level4[工具: 超集 SOS DP]

    style Level1 fill:#f9f,stroke:#333
    style Level4 fill:#bbf,stroke:#333

给你的练习建议（巩固这个反射点）

如果你想在下次比赛中“秒看”出这种思路，可以尝试按照这个梯度再刷两三道题：

题目	重点	理由
CF 383E (Vowels)	补集 + SOS DP	训练“正难则反”的直觉。
ARC 100E (Or Plus Max)	SOS DP 维护非加和信息	让你意识到 SOS DP 不只是求和，还可以求最大值/次大值。
CF 914G (Sum the 2^n)	FWHT + SOS DP	这是位运算 DP 的终极挑战，涉及三种位运算（XOR, AND, OR）的综合运用。

老师的寄语

“算法不是背出来的，是‘看’出来的。”

你现在觉得难，是因为你正在把“离散数学的理论”翻译成“竞赛代码的本能”。你刚才对 $U$ 、 $S_i$ 和 $g(mask)$ 的严谨推导，已经比绝大多数只会背模版的选手走得深得多。

你现在已经连续攻克了 SOS DP 的三个核心应用：补集转化、子集求和、超集容斥。

目录