マジカル

Jur_Cai · 2023-03-07 20:34:23 · 个人记录

Reference

1. 二项式反演

二项式定理

(a+b)^n=\sum\limits_{i=0}^n{n\choose i}a^ib^{n-i}

典中典

对于排列 a，\forall a_i,a_i\ne i，求 a 的个数。

莎贝尔容斥

先随便填，但是其中有不满足要求的方案。

哪些方案不合法，\exists a_i,a_i=i

故减去钦定一个位置不合法，其他地方随便排的方案。

但是又会减重，例如有两个位置不合法就会被计算两次。

又要加上钦定两个位置不合法的情况。

这样就有 \mathcal O(2^n) 的做法了。

简单容斥

枚举子集太慢了，考虑组合数。

\sum\limits_{i=0}^n(-1)^i{n\choose i}(n-i)!

容斥的本质

\sum\limits_{i=0}^n(-1)^i{n\choose i}=(-1+1)^n=[n=0]

感性理解一下，上面那个题只有 n=0，即恰有 0 个人不合法的方案被统计，其他的都抵消了。

转一下形式

设 f(n) 为 n 个数随便填的方案数，g(n) 为 n 个数均不填在自己位置的方案数。

f(n)=\sum\limits_{i=0}^n{n\choose i}g(i)

以及我们上面的容斥式子

g(n)=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}f(i)

怎么推导

\begin{aligned} g(n) &=\sum\limits_{m=0}^n[n-m=0]{n\choose m}g(m)\\ &=\sum\limits_{m=0}^n\left( \sum\limits_{i=0}^{n-m}(-1)^i{n-m\choose i} \right){n\choose m}g(m)\\ &=\sum\limits_{m=0}^n \sum\limits_{i=0}^{n-m}(-1)^i{n\choose i} {n-i\choose m}g(m)\\ &=\sum\limits_{i=0}^n(-1)^i{n\choose i}\sum\limits_{m=0}^{n-i}{n-i\choose m}g(m)\\ &=\sum\limits_{i=0}^n(-1)^i{n\choose i}f(n-i)\\ &=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}f(i)\\ \end{aligned}

就得到了二项式反演的一种形式。

Another

上式中的 f(n) 可看作表示 “至多”，而当 f(n) 表示 “至少” 时也有类似结论。

f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)

g(n)=\sum\limits_{i=n}^m (-1)^{i-n}{i\choose n}f(i)

至此就可以把好算的至多至少，转为难算的恰好了。

注意这里定义的至少，表示的是钦定一组后统计方案再累加，会重复统计一种情况。

更好写的暴力递推

形式一

g_n=f_n-\sum\limits_{i=0}^{n-1}{n\choose i}g_i

形式二

g_n=f_n-\sum\limits_{i=n+1}^m{i\choose n}g_i

如果式子系数是简单的，可以直接套用这个反演方式。

2839. 集合计数
$f(i)$ 很好算，钦定 $i$ 个元素之后，其他元素可选可不选，有 $2^{n-i}$ 个子集，再在其中选若干个，即 $2^{2^{n-i}}$ 中方案。二项式反演一下就好了

f(i)={n\choose i}2^{2^{n-i}}

g(k)=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}{n\choose i}2^{2^{n-i}}

直接算即可。

P4859 已经没有什么好害怕的了

原题保证 2n 个数两两不同。

注意要求的是 A>B 比 B>A 的个数多恰好 k 个的方案数。

所以实际上求的是 A>B 的个数恰好是 \frac{n+k}{2}

一眼二项式反演，考虑求钦定 i 个的方案数。

先将 A,B 都排个序。

dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times(cnt_i-j+1)

$cnt_i$ 表示比 $A_i$ 小的 $B_i$ 的个数，随便双指针求。 - ## [P5505 [JSOI2011]分特产](https://www.luogu.com.cn/problem/P5505) 每种特产是独立的，想要放到一起直接算很困难。对于一种特产，不必分到每一个人，而最后要求每个人都能发到，考虑反演。 $g(i)$ 表示恰好有 $i$ 个人没分到，$f(i)$ 表示钦定了 $i$ 个人分不到的方案数。对于一种特产隔板法算一下就好。 $$ f(i)={n\choose i}\prod\limits_{j=1}^m{a_j+n-i-1\choose n-i-1} $$ 最后答案 $$ g(0)=\sum\limits_{i=0}^n(-1)^{i-0}{i\choose0}f(i) $$ $$ g(0)=\sum\limits_{i=0}^n(-1)^{i}{n\choose i}\prod\limits_{j=1}^m{a_j+n-i-1\choose n-i-1} $$ - ## [CF1228E Another Filling the Grid](https://www.luogu.com.cn/problem/CF1228E) 只考虑行的限制是好做的，一行的方案数是 $k^n-(k-1)^n$。接下来想满足列的限制，很难直接处理。那就钦定 $i$ 列不合法 $$ f(i)={n\choose i}\left(k^{n-i}(k-1)^i-(k-1)^n\right)^n $$ 反演一下得出答案 $$ g(0)=\sum\limits_{i=0}^n(-1)^{i-0}{i\choose 0}f(i) $$ $$ g(0)=\sum\limits_{i=0}^n(-1)^i{n\choose i}\left(k^{n-i}(k-1)^i-(k-1)^n\right)^n $$ --- --- --- # 2. 莫比乌斯反演 ## 莫比乌斯函数 $$ x=\prod\limits_{i=1}^k p_i^{c_i},\,p_i\in\mathbb{P},c_i\ge1 $$ $$ \mu(x)= \begin{cases} 1 & x=1 \\ 0 & \exists i\in[1,k],\,c_i>1 \\ (-1)^k & \forall i\in[1,k],\,c_i=1 \\ \end{cases} $$ ## 有什么性质 $$ \sum\limits_{d\mid n}\mu(d)= \begin{cases} 1 & n=1 \\ 0 & n\ne1 \\ \end{cases} $$ 证明先设 $n=\prod\limits_{i=1}^kp_i^{c_i}$，$n'=\prod\limits_{i=1}^kp_i

\sum\limits_{d\mid n}\mu(d) =\sum\limits_{d\mid n'}\mu(d) =\sum\limits_{i=0}^k{k\choose i}(-1)^i =[k=0]=[n=1]

所以还有

[\gcd(i,j)=1]=\sum\limits_{d\mid\gcd(i,j)} \mu(d)

与狄利克雷卷积

\varepsilon(n)=\sum\limits_{d\mid n}\mu(d),\,\mu\ast 1=\varepsilon

还可以推导得到

(\varphi\ast 1)(n)=n,\,\varphi(n)=\sum\limits_{d\mid n}d\times\mu\left(\frac{n}{d}\right)

有什么用？

反演

f(n)=\sum\limits_{d\mid n} g(n)

g(n)=\sum\limits_{d\mid n}\mu(d)f\left(\frac{n}{d}\right)

证明

如法炮制

\begin{aligned} g(n) &=\sum\limits_{m\mid n}\left[\frac{n}{m}=1\right]g(m)\\ &=\sum\limits_{m\mid n}\sum_{d\mid\frac{n}{m}}\mu(d)g(m)\\ &=\sum\limits_{d\mid n}\mu(d)\sum_{m\mid\frac{n}{d}}g(m)\\ &=\sum\limits_{d\mid n}\mu(d)f\left(\frac{n}{d}\right)\\ \end{aligned}

Another

f(n)=\sum\limits_{n|d} g(d)

g(n)=\sum\limits_{n|d}\mu\left(\frac{d}{n}\right)f(d)

莫比乌斯反演扩展

OI-wiki 没给题，也找不到，先随便记一下。

t$ 是完全积性函数，且 $t(1)=1

f(n)=\sum_{i=1}^n t(i)g\left(\left\lfloor\frac ni\right\rfloor\right)

g(n)=\sum_{i=1}^n \mu(i)t(i)f\left(\left\lfloor\frac ni\right\rfloor\right)

P2522 [HAOI2011]Problem b

先差分，题意就变成求 \sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=k]

开始操作

\begin{aligned} &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=k]\\ &=\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]\\ &=\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum\limits_{d\mid \gcd(i,j)}\mu(d)\\ &=\sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d\mid i]\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d\mid j]\\ &=\sum\limits_{d=1}\mu(d)\left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor\\ \end{aligned}

整除分块求一求。

P1829 [国家集训队]Crash的数字表格

先转 \gcd，枚举 \gcd。
\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,d\mid j,\gcd(\frac id,\frac jd)=1} \frac{i\times j}{d} \sum_{d}d\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}[\gcd(i,j)=1] \,i\times j
问题转化为求
F(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1] \,i\times j
莫比乌斯变化一下
\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid \gcd(i,j)} \mu(d)\cdot i\cdot j \sum_{d}\mu(d)\cdot d^2\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor} i\cdot j
前半部分前缀和，然后又转化求后半部分
G(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m} i\cdot j=\frac{n(n+1)}{2}\times\frac{m(m+1)}{2}
带回去
F(n,m)=\sum_d\mu(d)\cdot d^2\cdot G\left(\left\lfloor\frac nd\right\rfloor,\left\lfloor\frac md\right\rfloor\right)
哇哇哇整除分块。

带回去
Ans=\sum_d d\cdot F\left(\left\lfloor\frac nd\right\rfloor,\left\lfloor\frac md\right\rfloor\right)
哇哇哇整除分块。
P3327 [SDOI2015]约数个数和

首先有性质 d(i\cdot j)=\sum\limits_{x\mid i}\sum\limits_{y\mid j}[\gcd(x,y)=1]

证明很高妙。考虑一个 k\mid (i\cdot j) 的一个因子 p^c，i 中有 p^a，j 中有 p^b。

若 c\le a 那就在 a 中选择 c 个；若 c>a 那就在 b 中选择 c-a 个。

这样每个因子都可以对应到一种选择方案。

然后就可以开始推式子了
\begin{aligned} d(i\times j) &=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]\\ &=\sum_{x\mid i}\sum_{y\mid j}\sum_{p\mid \gcd(x,y)}\mu(p)\\ &=\sum_{p\mid i,p\mid j}\mu(p)\sum_{x\mid i}\sum_{y\mid j}[p\mid \gcd(x,y)]\\ &=\sum_{p\mid i,p\mid j}\mu(p)\sum_{x\mid \frac ip}\sum_{y\mid \frac jp}1\\ &=\sum_{p\mid i,p\mid j}\mu(p)\cdot d\left(\frac ip\right)d\left(\frac jp\right)\\ \end{aligned}
带回到原式中
\begin{aligned} \sum_{i=1}^n\sum_{j=1}^md(i\times j) &=\sum_{i=1}^n\sum_{j=1}^m\sum_{p\mid i,p\mid j}\mu(p)\cdot d\left(\frac ip\right)d\left(\frac jp\right)\\ &=\sum_{p}\sum_{i=1}^n\sum_{j=1}^m[p\mid i][p\mid j]\cdot\mu(p)\cdot d\left(\frac ip\right)d\left(\frac jp\right)\\ &=\sum_{p}\sum_{i=1}^{\lfloor\frac np\rfloor}\sum_{j=1}^{\lfloor\frac mp\rfloor}\mu(p)\cdot d(i)\cdot d(j)\\ &=\sum_{p}\mu(p)\sum_{i=1}^{\lfloor\frac np\rfloor}d(i)\sum_{j=1}^{\lfloor\frac mp\rfloor}d(j) \end{aligned}
注意到这是前缀和，可以预处理。

哇哇哇整除分块
More More Tea Tea

3. Min-Max 容斥

不知道二级标题写什么

\max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}\min(T)

\min(S)=\sum_{T\subseteq S}(-1)^{|T|-1}\max(T)

证明

设 a_k 为全集稳定排序后第 k 大，\min(S)=a_k。

当 k=1 时，易得到 S={a_1}。

当 k\ne1 时，\forall i\in[k+1,n],a_i\notin S，[1,k-1] 可以随便选，通过人类智慧可得，2^{k-2} 种方案 |S| 是奇数，其余是偶数，因为贡献都是 a_k 乘个系数就消掉了。

所以只有当 \max(S)=\min(S) 的贡献才会统计进去。

期望相关

就用 E(\max(S)) 和 E(\min(T))，替换 \max(S) 和 \min(T)。

注意期望的 \max/\min 不能大力拆，即 E(\max(a,b))\ne \max(E(a),E(b))

扩展形式

\operatorname{kthmax}(S)=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}\min(T)

\operatorname{kthmin}(S)=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}\max(T)

证明可以参照一般形式推广

另一形式

\operatorname{lcm}(S)= \prod_{T\subseteq S}\gcd(T)^{(-1)^{|T|-1}}

可以看做是对指数做的容斥。

P3175 [HAOI2015]按位或
注意到 $P(\min(T)=k)=P(S\oplus T)^{k-1}\times(1-P(S\oplus T)) 由 $P(x=k)=p\times(1-p)$，可以得到 $E(x)=\frac 1p
所以就易得期望式子，问题就只需要处理一个子集前缀和就可以了。
P4707 重返现世

发现和上一题很像，但是变成了 kth

发现 |n-k|\le10，\min_k=\max_{n-k+1}

将 k 变为 n-k+1，相当于要求 \sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}\min(T)。

数据范围不支持直接来了，考虑 dp。
$f_{i,j}$ 表示考虑了前 $i$ 个物品，$\sum p=m$ 的答案。组合数没法转移，考虑递推式 ${n\choose m}={n-1\choose m}+{n-1\choose m-1}$。即 $k$ 需要进状态，再进行一个容斥系数的乘 $$ f_{k,i,j}=f_{k,i-1,j}+f_{k-1,i-1,j-p_i}-f_{k,i-1,j-p_i} $$ 长得像背包，同样可以用类似方法把 $i$ 那一维优化掉。当由空集转移的时候特判一下即可。 - ## [P7360 「JZOI-1」红包](https://www.luogu.com.cn/problem/P7360) 直接对 min-max 容斥式子不是很容易做。但是注意到 $f(n,k)=\prod\limits_{i_1=1}^n\prod\limits_{i_2=1}^n\cdots\prod\limits_{i_k=1}^n\gcd(i_1,i_2,\cdots,i_k)$ 是容易算的。别把答辩放在指数上。 $$ f(n,k)=\prod_{D=1}^nD^{\sum_{d=1}^{\lfloor n/D\rfloor}\mu(d)\lfloor\frac n{Dd}\rfloor^k} =\prod_{D=1}^n\prod_{d=1}^{\lfloor\frac nD\rfloor}D^{\mu(d)\lfloor\frac n{Dd}\rfloor^k} $$ 考虑一个 $f(n,i)$ 对整个答案的贡献，除了钦定的 $i$ 个位置，其他位置随便填，都会在枚举子集的时候把这个计入答案。 $$ \prod_{i=1}^k f(n,i)^{(-1)^{i-1}\times{k\choose i}n^{k-i}} $$ 直接把 $f$ 带进去没有什么化简思路，但是注意到改变的值只有 $k f(n,k)=\left(\prod_{D=1}^n\prod_{d=1}^{\lfloor\frac nD\rfloor}D^{\mu(d)}\right)^{\lfloor\frac n{Dd}\rfloor^k}
指数很烦，再变一下
f(n,k)=\prod_{D=1}^n\left(\prod_{d\mid D}d^{\mu(\frac Dd)}\right)^{\lfloor\frac n{D}\rfloor^k}
带进去
\prod_{i=1}^k\left(\prod_{D=1}^n\left(\prod_{d\mid D}d^{\mu(\frac Dd)}\right)^{\lfloor\frac n{D}\rfloor^i}\right)^{(-1)^{i-1}{k\choose i}n^{k-i}} \prod_{D=1}^n\prod_{i=1}^k\left(\prod_{d\mid D}d^{\mu(\frac Dd)}\right)^{\lfloor\frac n{D}\rfloor^i(-1)^{i-1}{k\choose i}n^{k-i}}
现在就只要计算那坨指数加起来
\begin{aligned} &=\sum_{i=1}^k(-1)^{i-1}{k\choose i}n^{k-i}\times\left\lfloor\frac n{D}\right\rfloor^i\\ &=n^k-\sum_{i=0}^k(-1)^{i}{k\choose i}n^{k-i}\times\left\lfloor\frac n{D}\right\rfloor^i\\ &=n^k-\left(n-\left\lfloor\frac n{D}\right\rfloor\right)^k \end{aligned}
回带
ans=\prod_{D=1}^n\left(\prod_{d\mid D}d^{\mu(\frac Dd)}\right)^{n^k-\left(n-\left\lfloor\frac n{D}\right\rfloor\right)^k}
设 g(n)=\prod_{d\mid n}d^{\mu(\frac nd)}，可以 \mathcal O(n\log n) 预处理，也可以推推性质 \mathcal O(n)。

整除分块算一算，\mathcal O(T\sqrt n\log k)。

4. 集合反演

找点普通的感觉

有数列 a_{1\sim2^n-1}，b_{1\sim2^n-1}，求数列 c 其中

c_r=\sum_{p,q}[p \operatorname{or} q=r]a_pb_q

这不是

把下标看成集合，那产生贡献的条件是 p\cup q=r，但并不好处理。

注意到 [p\cup q\subseteq s]=[p\subseteq s][q\subseteq s]。

对于数列 a，定义 a' 满足 a'_s=\sum_{p\subseteq s}a_p。

求 a' 就是一个高维前缀和。

\begin{aligned} c'_r &=\sum_{p,q}[p \cup q\subseteq r]a_pb_q\\ &=\sum_{p\subseteq r}a_p\sum_{q\subseteq r}b_q\\ &=a'_rb'_r \end{aligned}

已知 c' 求 c，反演！

但其实很无脑，倒着减一遍就好了。

数学推导，找找性质。

\sum_{r\subseteq p}(-1)^{|r|}=[p=0]

本质是二项式反演。

\begin{aligned} g(p) &=\sum_{q\subseteq p}[p-q=0]g(q)\\ &=\sum_{q\subseteq p}\sum_{r\subseteq p-q}(-1)^{|r|}g(q)\\ &=\sum_{r\subseteq p}(-1)^{|r|}\sum_{q\subseteq p-r}g(q)\\ &=\sum_{r\subseteq p}(-1)^{|r|}f(p-r) \end{aligned}

最后就有这样的结论了

f(S)=\sum_{T\subseteq S}g(T)

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

Another

c_r=\sum_{p,q}[p\operatorname{and}q=r]a_pb_q

可以取反后做 \operatorname{or}

做超集和变化，不难推出类似做法

也能得到如下结论

f(S)=\sum_{S\subseteq T}g(T)

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

多重子集反演

同上，集合变为可重集。

f(S)=\sum_{T\subseteq S} g(T)

定义 \mu(S)，若 S 中存在相同元素时为 0，否则为 (-1)^{|s|}。

可以得到 \sum\limits_{T\subseteq S}\mu(T)=[S=0]

g(S)=\sum_{T\subseteq S}\mu(S-T)f(T)

所以莫比乌斯反演相当于是在质因数分解上集合反演。

## 反演的幕后观察一下，这个东西通过一个正变化，乘起来，再做一个逆变化，解决下标上运算奇怪的卷积。其实就是 FWT 的核心思想。但是多项式不考。 ## 子集卷积求 $c_r=\sum\limits_{p\subseteq r}a_pb_{r-p}$，$\mathcal O(n^22^n)

一个简单的想法是把 p\subseteq r 拆成 [p\cap q=0][p\cup q=r]，然后再分别把式子展开

c_r=\sum_{v\subseteq r}(-1)^{|r|-|v|}\sum_{0\subseteq u\subseteq v}(-1)^{|u|-|0|}\sum_{p}[u\subseteq p\subseteq v]a_p\sum_{q}[u\subseteq q\subseteq v]b_q

但是还是不太好做，多记录一维 c_{i,r}，表示 [|p|=i] 的和，这样就只有并集的条件了

\begin{aligned} c_{i,r} &=\sum_{p,q\subseteq r}[|p|=i][|q|=|r|-i][p\cup q=r]a_pb_q\\ &=\sum_{p,q\subseteq r}(-1)^{|r|-|v|}\sum_{p\subseteq r}[|p|=i]a_p\sum_{q\subseteq r}[|q|=|r|-i]b_q \end{aligned}

对于 c 构造出的变换就是对于每个 i 做一个子集前缀和。

P3349 [ZJOI2016]小星星

设 f(S) 表示至多用 S 中的颜色覆盖的方案数，g(S) 表示恰好用 S 中的颜色覆盖的方案数。

考虑一个树形 dp，f_{x,i} 表示以 x 为根的子树，x 颜色为 i 的方案数，转移枚举儿子填什么颜色。

反演一下求答案，\mathcal O(n^32^n)。

UOJ37 【清华集训2014】主旋律

正难则反，首先考虑转为求删边后缩点为 DAG 的方案数。

先做子问题，给一张图求删边后是 DAG 的方案数。

一个 DAG 一定存在入度为 0 的点，考虑设 z(T) 表示 T 恰好是入度为 0 点集的方案数，d(T) 表示钦定 T 是入度为 0 点集的方案数。

设 f(S) 是点集为 S 的答案，c(S,T) 表示 S 向 T 边的个数。

易知 d(T)=2^{c(T,S-T)}f(S-T)，又有 f(S)=\sum_{T\subseteq S,T\ne\varnothing}z(T)，简单集合反演得到
\begin{aligned} f(S) &=\sum_{T\subseteq S,T\ne\varnothing}\sum_{T\subseteq R\subseteq S}(-1)^{|R|-|T|}d(R)\\ &=\sum_{R\subseteq S,R\ne\varnothing}(-1)^{|R|}d(R)\sum_{T\subseteq R,T\ne\varnothing}(-1)^{|T|}\\ &=\sum_{R\subseteq S,R\ne\varnothing}(-1)^{|R|}d(R)([R=\varnothing]-1)\\ &=\sum_{R\subseteq S,R\ne\varnothing}(-1)^{|R|+1}2^{c(R,S-R)}f(S-R) \end{aligned}
回到原问题，外面要套一个枚举缩点方案，复杂度爆炸。

考虑在推出来的式子中把缩的点拆开，我们只需要计算 R 的缩点方案数，式子可以写成
f(S)=\sum_{R\subseteq S,R\ne\varnothing}\sum_{k=1}^{|R|}(-1)^{k+1}g_k(R)\times2^{c(R,S-R)}\times2^{c(S-R,S-R)} 对于 $k$ 的奇偶分开考虑，定义 $p(S)=\sum\limits_{k=1}^{\lfloor|T|+1/2\rfloor}g_{2k-1}(S)-\sum\limits_{k=1}^{\lfloor|T|/2\rfloor}g_{2k}(S)$。再定义一个 $dp(S)$ 表示 $S$ 构成一个 SCC 的方案数，即答案。 $$ p(S)=dp(S)-\sum_{T\subseteq S,T\ne\varnothing}dp(T)\times p(S-T) $$ 但是直接求是错的，发现会算重，那就需要钦定一位必选，这样转移上来就是对的。再扔回去 $$ f(S)=\sum_{T\subseteq S,T\ne\varnothing}p(T)\times 2^{c(R,S-R)+c(S-R,S-R)} $$ $$ dp(S)=2^{c(S,S)}-f(S) $$ 可以递推了

マジカル

1. 二项式反演

二项式定理

典中典

莎贝尔容斥

简单容斥

容斥的本质

转一下形式

怎么推导

Another

更好写的暴力递推

2839. 集合计数

P4859 已经没有什么好害怕的了

与狄利克雷卷积

有什么用？

证明

Another

莫比乌斯反演扩展

P2522 [HAOI2011]Problem b

P1829 [国家集训队]Crash的数字表格

P3327 [SDOI2015]约数个数和

More More Tea Tea

3. Min-Max 容斥

不知道二级标题写什么

证明

期望相关

扩展形式

另一形式

P3175 [HAOI2015]按位或

P4707 重返现世

4. 集合反演

找点普通的感觉

这不是

Another

多重子集反演

P3349 [ZJOI2016]小星星

UOJ37 【清华集训2014】主旋律