数学-子集反演
Filberte
·
·
算法·理论
反演公式
有一个集合 [n]，有两个函数 f 和 g，定义域都是 [n] 的子集。
结论
若已知 f(S) = \sum\limits_{T\subseteq S} g(T)，则 g(S) = \sum\limits_{T\subseteq S} (-1)^{|S| - |T|}f(T)。
证明
（后三行的 s 就是 S\text{\\}Q）
\begin{aligned}
\sum\limits_{T\subseteq S} (-1)^{|S| - |T|}f(T)
&= \sum\limits_{T\subseteq S} (-1)^{|S| - |T|}\cdot\sum\limits_{Q\subseteq T} g(Q)\\
&= \sum\limits_{Q\subseteq S} g(Q) \sum\limits_{Q\subseteq T\subseteq S} (-1)^{|S| - |T|}\\
&= \sum\limits_{Q\subseteq S} g(Q) \sum\limits_{T\subseteq (S-Q )}(-1)^{|S-Q|-|T|}\\
&= \sum\limits_{Q\subseteq S} g(Q) \sum\limits_{i = 0}^{|s|} (-1)^{|s| - i}\binom{|s|}{i} 1^i \\
&= \sum\limits_{Q\subseteq S} g(Q) \cdot(1-1)^{|s|} \\
&= \sum\limits_{Q\subseteq S} g(Q) \cdot (s = \varnothing) \\
&=g(S)
\end{aligned}
简单解释一下，第一行是根据定义写出的，第二行是交换了一下求和时的枚举顺序，第三行是因为 Q \subseteq T，所以不如干脆先从 S 中去掉 Q，第 4 行开始发现 \sum\limits_{T\subseteq (S-Q )}(-1)^{|S-Q|-|T|} 的值只跟 T 的大小有关，所以枚举 T 的大小，最后用二项式定理，发现在 S \not= Q 的情况下后边的求和式都是 0，实际上只在 Q = S 的意义下有意义，就 得到了需要证明的结论。
推论
若已知 f(S) = \sum\limits_{T\supseteq S} g(T)，则 g(S) = \sum\limits_{T\supseteq S} (-1)^{|S| - |T|}f(T)。证明与上文类似，不多赘述。
再给 2 个显然的结论。
\begin{aligned}
(-1)^{x - y} &= (-1)^{x+y}\\
(-1)^{(2x + k)} &= (-1)^{k}
\end{aligned}
二项式定理易证的：
\begin{aligned}
\sum\limits_{S\subseteq T} (-1)^{|S|} &= 0\\
\sum\limits_{i = 0}^{\frac{n}{2}} \binom{n}{2i} &= \sum\limits_{i = 0}^{\frac{n}{2}} \binom{n}{2i-1}
\end{aligned}
找不到原题了
题意描述：T 组数据，每组数据给定 n,m ，再给 m 个数 a_1 \sim a_m，问 1 \sim n 中有多少个数被奇数个 a_i 整除。其中 T \le 10^3,n \le 10^5,m \le 15。
定义两个函数：对于 \{1,2\dots m\} 的一个子集 S = {i_1,i_2\dots i_k}，
$g(S)$ 表示有多少个 $x$，满足 $1\le x\le n$，且 $x$ **仅被** $a_{i_1},a_{i_2}\dots a_{i_k}$ 整除。
显然，$f(s) = \left\lfloor\dfrac{n}{\mathrm{lcm}(a_{i_1},a_{i_2}\dots a_{i_k})}\right\rfloor$，且可以用 $g$ 来表示 $f$ ，$f(S) = \sum\limits_{T\supseteq S} g(T)$。
根据子集反演公式：$g(S) = \sum\limits_{T\supseteq S}(-1)^{|S|-|T|} \cdot f(T)
\begin{aligned}
\sum\limits_{|S| odd} g(S) &= \sum\limits_{|S| odd}\sum\limits_{T\supseteq S}(-1)^{|S|-|T|} \cdot f(T)\\
&= \sum\limits_{T\ne\varnothing}f(T)\sum\limits_{|S| odd \land S \subseteq T}(-1)^{|S| + |T|}\\
&=\sum\limits_{T\ne\varnothing}f(T)\sum\limits_{i = 1}^{\left\lfloor\frac{|T|}{2}\right\rfloor}\binom{|T|}{2i -1}(-1)^{|T|+2i-1}\\
&=\sum\limits_{T\ne\varnothing}f(T)\cdot(-1)^{|T|-1} \cdot2^{|T|-1}\\
&=\sum\limits_{T\ne\varnothing}f(T)\cdot(-2)^{|T|-1}
\end{aligned}
所以就可以在 O(2^m) 的复杂度内求出答案了。
BZOJ-2863
考虑 \{1,2\dots n\} 的一个子集 S，以 f_n(S) 有多少个不同的 DAG，使得 S 这个集合中的点入度为 0； g_n(S) 表示有多少个不同的 DAG，使得有且仅有 S 这个集合中的点入度为 0。答案状态是 f_n(\varnothing)，也就是除了 DAG 这个要求之外，没有其他任何限制。
$$
f_n(S) = 2^{|s|\cdot(n-|s|)} \cdot f_{n-|s|}(\varnothing)
$$
可以用 $g$ 来表示 $f$：
$$
f_n(S) = \sum\limits_{T\supseteq S} g_n(T)
$$
这就是子集反演的形式了。但在开始反演之前，需要先进行一个观察：$g_n(\varnothing) = 0$。因为在一个 DAG 中，总会有节点的入度是 $0$，所以在考虑状态的时候，可以把这个状态剔除。
同时，需要了解另一个结论：$(-1)^{x + y} = (-1)^{x-y}$，这是因为两者的商 $(-1)^{2y} = 1$。
$$
\begin{aligned}
f_n(\varnothing)
&= \sum\limits_{S\not =\varnothing} g_n(S)\\
&= \sum\limits_{S\not =\varnothing}\sum\limits_{T\supseteq S}(-1)^{|T|-|S|}\cdot f_n(T)\\
&= \sum\limits_{S\not =\varnothing}\sum\limits_{T\supseteq S}(-1)^{|T|-|S|}\cdot2^{|T|\cdot(n-|T|)} \cdot f_{n-|T|}(\varnothing)\\
&= \sum\limits_{T\not=\varnothing}[\sum\limits_{S\subsetneq T}(-1)^{|S|}]\cdot(-1)^{|T|}\cdot2^{|T|\cdot(n-|T|)} \cdot f_{n-|T|}(\varnothing)\\
&= \sum\limits_{T\not=\varnothing}(-1)^{|T| + 1}\cdot2^{|T|\cdot(n-|T|)} \cdot f_{n-|T|}(\varnothing)\\
&= \sum\limits_{k = 1}^{n} \binom{n}{k}(-1)^{k+1}\cdot2^{k(n-k)}\cdot f_{n-k}(\varnothing)
\end{aligned}
$$
也就是说，其实我们只需要计算出 $S=\varnothing$ 的状态即可，可以重新定义 $f$ 函数了：$f(n)$ 表示 $n$ 个点的 DAG 有多少个，我们有 $O(n^2)$ 的递推公式如下，可以通过此题。
$$
f(n) = \sum\limits_{k = 1}^n \binom{n}{k}(-1)^{k+1}\cdot2^{k(n-k)}\cdot f_{n-k}
$$
这个式子可以通过指数型生成函数配合多项式求逆进一步优化到 $O(n\log n)$，但这篇学习笔记主要是记录子集反演相关的，就不做进一步优化了（主要是我不会）。
代码：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 3050;
int n;
const int mx = 1e6;
int p2[mx + 10], f[N], c[N][N];// fac[i] = i * (n - i), c[i] = C(n, i);
int qpow(int b){
if(b <= mx) return p2[b];
int x = qpow(b >> 1);
x = x * x % mod;
if(b & 1) x = (x << 1) % mod;
return x;
}
signed main(){
cin >> n;
p2[0] = 1;
for(int i = 1;i <= mx;i++) p2[i] = p2[i - 1] * 2 % mod;
c[0][0] = 1;
for(int i = 1;i <= n;i++){
c[i][0] = 1;
for(int j = 1;j <= i;j++){
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
f[0] = 1;
for(int i = 1;i <= n;i++){
int sum = 0;
for(int j = 1;j <= i;j++){
int x = (j & 1) ? 1 : -1;
sum = ((sum + c[i][j] * qpow((i - j) * j) % mod * f[i - j] % mod * x) % mod + mod) % mod;
}
f[i] = sum;
}
cout << f[n] << "\n";
return 0;
}
```