[学习笔记] 各种反演

目录
  • 1. 子集反演
    • 1.1. 理解与证明
      • 1.1.1. 形式零
      • 1.1.2. 形式贰
    • 1.2. 例题
  • 2. 二项式反演
    • 2.1. 理解与证明
      • 2.1.1. 形式零
      • 2.1.2. 形式壹
      • 2.1.3. 形式贰
    • 2.2. 一些题

1. 子集反演

1.1. 理解与证明

1.1.1. 形式零

\[f(S)=\sum_{T\subseteq S}g(T)\Leftrightarrow g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T) \]

首先我们知道 \(\sum_{i=0}^n (-1)^i\cdot \binom{n}{i}=[n=0]\)（二项式定理），不妨将 \(|S|\) 看作 \(n\)，将选 \(|T|=i\) 的集合看作 \(\binom{n}{i}\)，那么就有 \(\sum_{T\subseteq S}(-1)^{|T|}=[S=\empty]\). 那么

\[\begin{aligned} g(S)&=\sum_{T\subseteq S}[S\setminus T=\empty]\cdot g(T)\\ &=\sum_{T\subseteq S}\sum_{Q\subseteq S\setminus T}(-1)^{|Q|}\cdot g(T)\\ &=\sum_{Q\subseteq S}(-1)^{|Q|}\cdot \sum_{T\subseteq S\setminus Q}g(T)\\ &=\sum_{Q\subseteq S}(-1)^{|Q|}\cdot f(S\setminus Q)\\ \end{aligned} \]

结论得证。另外反方向也有相似的形式，就不予证明了。

1.1.2. 形式贰

也叫多重子集反演，此时 \(S,T\) 变成了多重集。定义 \(\varphi(S)\) 为当 \(S\) 包含重复元素时为零，否则为 \((-1)^{|S|}\). 那么同样有：\(\sum_{T\subseteq S}\varphi(T)=[S=\empty]\). 类似上文的证明，可以得到：

\[g(S)=\sum_{T\subseteq S}\varphi(S\setminus T)\cdot f(T) \]

1.2. 例题

例 1. \(\text{[ZJOI 2016] }\)小星星

朴素 \(\mathtt{dp}\) 是令 \(dp_{i,j,S}\) 表示点 \(i\) 的子树，点 \(i\) 的映射为 \(j\)，点 \(i\) 的子树映射集合为 \(S\) 的方案数。对于每个根 \(u\)，新建 \(f(u,S)\) 来合并子树信息，单次合并 \(\mathcal O(3^n)\)，总时间复杂度是 \(\mathcal O(n\cdot 3^n)\) 的。

算法瓶颈在于保证所有点的映射组成长度为 \(n\) 的排列。所以不妨设 \(g(S)\) 为 \(n\) 个点映射 恰好 使用 \(S\) 中所有点（不保证映射为排列），设 \(f(S)\) 为 \(n\) 个点映射 至多 使用 \(S\) 中所有点（不保证映射为排列）。那么

\[f(S)=\sum_{T\subseteq S}g(T)\Rightarrow g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}\cdot f(T) \]

最终答案为 \(g(U)=\sum_{S\subseteq U}(-1)^{n-|S|}\cdot f(S)\).

2. 二项式反演

2.1. 理解与证明

2.1.1. 形式零

\[f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n (-1)^i\binom{n}{i}f(i) \]

先看看多步容斥：

\[|A_1\cup A_2\cup...\cup A_n|=\sum\limits_{1\le i\le n}|A_i|-\sum\limits_{1\le i

\(A_i\) 表示满足条件 \(i\) 的元素集合，最终求得的结果只能是 "至少满足一个条件的元素集合" 或 "一个条件都不满足的元素集合"。这个柿子的证明就是考虑一个元素在左边与右边的贡献。

多数时候我们要求的是 "满足所有条件的元素集合"，所以需要用到一个性质 —— 集合的并等于补集的交的补集。

\[|A_1^c\cap A_2^c\cap ...\cap A_n^c|=|S|-\sum\limits_{1\le i\le n}|A_i|+\sum\limits_{1\le i

\[|A_1\cap A_2\cap ...\cap A_n|=|S|-\sum\limits_{1\le i\le n}|A_i^c|+\sum\limits_{1\le i

考虑一种特殊的情况：集合的交集大小只和集合个数有关。令 \(f(n),g(n)\) 分别为 \(n\) 个原集/补集的交集大小。上面的式子就可以转化为形式零，其中 \(f(0)=g(0)=|S|\).

实际上，二项式反演只是子集反演的一种特殊形式，所以我们也可以用类似的思路来证明：

\[\begin{aligned} g(n)&=\sum_{m=0}^{n}[n-m=0]\cdot \binom{n}{m}\cdot g(m)\\ &=\sum_{m=0}^{n}\sum_{k=0}^{n-m}(-1)^k\cdot \binom{n-m}{k}\binom{n}{m}\cdot g(m)\\ &=\sum_{k=0}^{n}(-1)^k\binom{n}{k}\cdot \sum_{m=0}^{n-k}\binom{n-k}{m}\cdot g(m)\\ &=\sum_{k=0}^{n}(-1)^k\cdot \binom{n}{k}\cdot f(n-k)\\ \end{aligned} \]

如果有多维呢？实际上是一样的，将 \(-1\) 和组合数系数相乘即可。

2.1.2. 形式壹

\[f(n)=\sum_{i=m}^n \binom{n}{i}g(i)\Leftrightarrow g(n)=\sum_{i=m}^n (-1)^{n-i}\binom{n}{i}f(i) \]

还是利用套路性的证明：

\[\begin{aligned} g(n)&=\sum_{i=m}^{n}[n-i=0]\cdot \binom{n}{i}\cdot g(i)\\ &=\sum_{i=m}^{n}\sum_{j=0}^{n-i}(-1)^j\cdot \binom{n-i}{j}\binom{n}{i}\cdot g(i)\\ &=\sum_{j=0}^{n}(-1)^j\binom{n}{j}\cdot \sum_{i=m}^{n-j}\binom{n-j}{i}\cdot g(i)\\ &=\sum_{j=0}^{n}(-1)^j\cdot \binom{n}{j}\cdot f(n-j)\\ \end{aligned} \]

由于 \(f\) 函数的限制，\(n-j\ge m\)，所以有

\[g(n)=\sum_{i=m}^n (-1)^{n-i}\binom{n}{i}f(i) \]

这也是之后会用到的 "至多式"。

2.1.3. 形式贰

\[f(n)=\sum_{i=n}^m \binom{i}{n}g(i)\Leftrightarrow g(n)=\sum_{i=n}^m (-1)^{i- n}\binom{i}{n}f(i) \]

这也是之后会用到的 "至少式"。

2.2. 一些题

例 1. \(\text{[NOI Online #2] }\)游戏

考虑 "钦定 \(k\) 次非平局" 枚举到的 "恰好 \(k'\) 次非平局" 满足 \(k’>k\)，我们考虑用第三个反演：设 \(f(n)\) 为钦定 \(n\) 次非平局的方案数，\(g(n)\) 为恰好 \(n\) 次非平局的方案数。

对于 \(f(n)\) 的求法，令 \(dp_{i,j}\) 为在 \(i\) 的子树内钦定 \(j\) 次非平局的方案数。用树型背包转移（之前在博客证明过）是 \(\mathcal O(n^2)\) 的。注意还要做 \(i\) 和子树内未匹配点的匹配。

例 2.

太长了，新开了一篇博客。

数论数学数论数学-二项式反演

相关

标签