2.29 讲课 笔记

开头的容斥的证明被咕咕咕了。

FMT

给定数列$a_{0\dots 2^{k}-1}$求$b$满足$b_{s} = \sum_{i\in s} a_i$

实现方法很简单，

for( i in 0..n-1 ) 
	for( j in 0..2^n-1)
		if( j & ( 1 << i ) ) 
			a[j] += a[j ^ ( 1 << i )]

然后称为$B = FMT(A)$，快速莫比乌斯变换

想要还原也很简单，把代码反着写：

for( i in n-1 downTo 0 ) 
	for( j in 2^n - 1 downTo 0)
		if( j & ( 1 << i ) ) 
			a[j] -= a[j ^ ( 1 << i )]

当然，$i$的顺序可以是原来的顺序，因为按照哪个顺序枚举位根本不重要

同时，$j$的顺序也不重要，考虑对于一个数字，它只有在当前枚举的位数为 1 的时候才被执行，所以就算已经枚举到这位是 0 的状态，它也不会被更新。

这样$A = IFMT( B )$

FMT 可以写成 FFT 那样的形式，就不赘述了。

或卷积

或卷积就需要用到这个东西。

或卷积是指：

$$C_x = \sum_{i|j=x} A_i B_j$$

有一个结论，$FMT(C) = FMT(A) + FMT(B)$

原因是$(i | j) = s$等价于$(i \sube s) and (j \sube s)$

所以有$C = IFMT( FMT(A) + FMT(B) )$

于是可以$O(n2^n)$做这个。

子集卷积

子集卷积张这样：

$$C_s = \sum_{i|j=s,i\&j = 0} A_i B_j$$

如果设$p(x)$为$x$的 popcount ，那么：

$$(i|j = s) , (i\&j = 0) \Leftrightarrow i|j = s , p(i)+p(j) = p(s)\\C_s = \sum_{i|j = s , p(i)+p(j) = p(s)} A_iB_j$$

我们把$c$扩展到二维，设$c’_{p,k}$，定义如下：

$$c'_{p,s} = \sum_{i|j = s,p(i)+p(j) = p} a_ib_j[p(s) = p]$$

把$c$扩展到二维了，$a$也需要扩展到二维，所以定义$a’_{p,s}$

$$a'_{p,s} = \left\{\begin{aligned}&0 & {p(s) \neq p}\\&a_{s} & {p(s) = p} \end{aligned}\right.$$

同理定义$b’_{p,s}$

我们知道

$$c'_{p,s} = \sum_{i|j = s,p(i)+p(j) = p} a'_{p(i),i} b'_{p(j),j}$$

观察到$c’_p = \sum_{i=0}^p a’_{i}\times_{or} b’_{p-i}$，而且需要去掉左边的$p(s) \neq p$的情况。

这样复杂度$O(n^3 2^n)$，一共要卷$n^2$次。

注意$FMT , IFMT$都有可加性，所以我们把那个或卷积写成$FMT$的形式

$$\begin{aligned}c'_{p} &= \sum_i IFMT(FMT(a'_i) · FMT(b'_{p-i}))\\&= IFMT( \sum_i FMT(a_i') · FMT(b_{p-i}') )\end{aligned}$$

我们现在只需要处理出所有$a’_i$和$b’_i$的卷积，最后再跑$n$次逆 FMT ，所以这样做就优化到了$O( 2^n n^2 )$

例题

无限次子集卷积，求全集是否为0

可以用类似的，分出 popcount 这一维的方法，做一些奇妙的事。

题目：数组$A$,已知$A_0 = 1$，算$B = A\times A \times \cdots A$，求$B_{2^n-1}$是否为 0。（这里的$\times$是子集卷积）

定义$c’_{p,s}$为$A$自乘无数次后，$s$这位是否为 0，且$s$的popcount为 p，同时定义$a’_{p,s}$若$p(s) = p$则为$a_s$否则为 0 ，其实就是跟前面那个子集 dp 类似的思路。

然后我们考虑，如果一个集合 最终 是 1 ，那么它一定可以划分成若干个子集，这些子集在$A$中都是 1，这是由子集卷积的定义得到的。所以我们考虑递推$c$

初始状态为$c’_{0,0} = 1$，假设我们已经算出了$c_{0\dots k-1}$需要算$c_k$递推过程为：

$$c'_k = \sum_{i=1}^k a_i' \times_{or} c'_{k-i}$$

哈密尔顿路径计数

给定一张$n$个点的无向图，求哈密尔顿路径个数。

经过每个点恰好一次，就是经过点数 len = n 并且每个点都有经过。

也就是说访问过的点集$V’$为全集$V$。

由于容斥原理，我们知道：

$$\sum_{T \sube S } (-1)^{|T|} = [S = \varnothing]$$

于是，我们把$[V\setminus V’ = \varnothing]$这么表示

$$\sum_{T \sube V\setminus V'} (-1)^{|T|} = [V \setminus V' = \varnothing] ​$$

然后我们设$P_S$表示必须经过$S$里面的所有点的方案数，所以

$$\begin{aligned}ans & =\sum_{F\sube V} [V\setminus F = \varnothing]P_F\\& = \sum_{F\sube V}(\sum_{T\sube V\setminus F} (-1)^{|T|} )P_F \end{aligned}$$

于是我们考虑对于每个集合$T$，$(-1)^T$的贡献是什么。不难发现，$T$的贡献就是对于每个$F \sube V \and T \cap F = \varnothing$ 的$P_F$求和，翻译成人话就是，不经过$T$ 中点的方案数量。

于是假设$C_S$表示不经过$S$中点且路径长度为$n$的方案数，于是最终我们有式子：

$$\sum_{T \sube V} (-1)^{|T|} C_T$$

这个$C$可以 dp 算，设$dp_{v,l}$表示$v$为终点，长度$l$的路径数。对于每个点集分别跑一次这个 dp 即可。

时间$O(n^2 2^n)$空间$O(nm)$

---

染色

题目：给定一张无向图，染色，问它是否可以相邻点不同颜色做到k染色。

卷积做法

$dp[i][S]$表示$i$种颜色染子集$S$是否可行。

枚举独立集$T$使得$T \cap S = \varnothing$所以可以转移到$dp[i + 1][T | S]$。形式化地：

$$dp[i + 1][j] = \sum_{k \sube j } dp[i][k] \times [j \setminus k 是独立集]$$

我们设$D[S] = [S 是独立集 ]$

那么$dp[i + 1] = dp[i] \times_{subset} D$

但是会发现改成或卷积只会让方案数量变多，不会产生原本做不到，现在做得到的情况。为什么呢，比如我们考虑子集卷积我们用$i$颜色染了$\{1,2,3\}$，$i + 1$染了$\{4,5\}$，用或卷积可能算上了$\{1,2,3\}\{3,4,5 \}$的情况，相当于用多个颜色染了一个点。但是由于集合内部仍然是独立集，所以这样染我们可以把重复染的点分配给这几个颜色之一的任何一种，同时如果显然原本就没方案可以做到 k 染色 最后一定也没办法做到，也就是说不会“无中生有”。所以直接转成或卷积是没问题的ww。

我们发现其实：

$$dp[i] = dp[0]\times D \times_{or} D \times_{or} D\times_{or} \cdots \times_{or} D(共 i 次)$$

所以写成 FMT 的形式：

$$FMT(dp[i]) = FMT(dp[0]) \cdot FMT^i(D)$$

复杂度是$O(n2^n)$

---

容斥做法

求是否存在独立集$T_{1\dots k}$使得两两不交且并集为$V$

同时我们有前面可知，我们可以去掉不交这个条件并且不会影响正确性。

然后类似前面哈密尔顿路径的充斥，考虑我们希望得到的$T$是$V \setminus (T_1 \cup \dots \cup T_k) = \varnothing$

然后由前面那个式子一样的推得到的东西，我们假设$C_S$表示不使用$S$中元素的到的$T_{1\dots k}$的个数，我们有了：

$$\sum_{S \sube V} (-1)^{|S|} C_S$$

显然的，我们有$C_S = {cnt^k_S}$其中$cnt_S$表示$S$的子集中独立集的个数。

同样地定义$D$有$cnt_S = FMT( D )$

所以你发现推出来式子和前面一样！

这样复杂度也是$O(n 2^n)$

---

其实这两种做法所做的事情是一样的，虽然推导过程不同。

考虑优化

注意到 我们只关心逆变换后$2^n-1$这一位，也就是$IFMT(A)_{2^{n}-1}$这个东西，考虑$x$对它的贡献，就是$(-1)^{popcount(inv(x))}$ ，其中$inv(x)$表示对$x$取反。

因为 IFMT 其实并不需要真正做，我们只需要枚举$2^n$个位置计算贡献即可得到需要的结果。

瓶颈在于$FMT^k(D)$

-$FMT(D)$：$dp[S]$表示$S$有多少个子集为独立集，也就是$FMT(D)$

• 任取$v \in S$讨论$v$是否在独立集中，$dp[S] = dp[S\setminus\{v\}] + dp[S \setminus (v\cup N(v))]$其中$N(u)$表示$u$相邻的点集。

  这样做只需要$O(2^n)$

• k 次方

  看起来需要ksm，需要$O(2^n\log k)$来解决每个位置，但是我们可以取比较小的$P$，然后预处理所有幂，这样处理复杂度依然是$O(2^n)$。

最终复杂度可以做到$O(2^n)$

---

由于掉线了很多，下面的内容很乱而且很可能有问题。。。（有时间再回来填坑吧）

给定图和关键点集，求所有斯坦纳树中的最小边个数

空间 16kb

经典的斯坦纳树，是$dp[rt][sta]$表示$rt$为根覆盖了$sta$的状态的关键点。

转移分为合并同根的斯坦纳树和扩展。具体实现见这里 以及以前写的巧克力。

所以我们可以二分最小边个数，变成存在性问题。

容斥视角

卡空间的核心思路在于和式中分开算每一项

$G$上的 Branching Walk 其实类似 一个 可以存在重复节点和重复边的 斯坦纳树，就是可以经过重复的点和边走过所有关键点。

我们的目的是存在性问题，所以可以直接对 branching walk 计数。如果我们有一个 branching walk 就可以通过所有点强行经过一次的方法来构造出斯坦纳树。

记$K$关键点集合，

$\sum_{S\sube K} (-1)^{|S|}C_S$,C_S 表 不经过关键点的braching walk的个数

$dp[rt][S][t]$表示以 rt 为根，禁止的关键点集$S$边数为$t$的 Branching Walk 个数。

转移的思路是割开一条 rt 到 T 的边

$rt \in r(S)$中时，如果$t = 0$显然为 1 ，否则$\sum_{T \in R(S) \cap N(rt)} \sum_{t_1+t_2=t-1} dp[rt][S][t_1]$

这个东西的转移实际上是两个老的转移合二为一的结果。

由于$S$总是没变，把$S$提到外面状态就是$dp[rt][t]$空间$O(n^2)$时间$O(2^nmn^2)$

---

卷积视角

卡空间的核心是把卷积转换成点积后每一项分开算

我们不再考虑 Branching Walk

判断的对象是 斯坦纳树，我们希望允许子树之间包含公共的节点。

这样弱化后的情况只会从一边多，并不会无中生有。但是注意在 容斥 里面是不能这样的，因为你不能去一变多，因为容斥包含减法，这样搞了会导致可能无解判成有解了。

但是对于卷积，相当于一个黑箱，不再需要去考虑一变多之类的。

$dp[rt][S][t]$以 rt 为根，包含了点集 S ，边数量为 t 的斯坦纳树的方案数。

$$dp[rt][S][t] = \sum_{T \in N(rt)}\sum_{t_1+t_2 = t}\sum_{S_1\cup S_2 = S , S_1\cap S_2 = \varnothing} dp[rt][S_1][t_1] \times dp[rt][S_2][t_2]$$

这样就变成了一个 dp 套 子集卷积 的形式。

还是考虑子集卷积弱化成或卷积，它仍然不会算漏。因为你考虑两个集合中有交的部分，可以划分给两个树之一，因此只会多算不会算漏。

$$dp[rt][S][t] = \sum_{T \in N(rt)}\sum_{t_1+t_2 = t}\sum_{S_1\cup S_2 = S , } dp[rt][S_1][t_1] \times dp[rt][S_2][t_2]$$

$dp[rt][t]$是一个数列，并且转移有顺序，是按照$t$升序转移。

$\forall (rt_1,t_1) , (rt_2,t_2), rt_1 ,rt_2 有边$，就可以用$dp[rt_1][t_1] \times_{or} dp[rt_2][t_2]$来更新

$dp[rt][t] = \sum_{rt_2相邻于 rt_1,t_1+t_2 = t-1} dp[rt][t_1] \times_{or} dp[rt_2][t_2]$

然后改写成 FMT

$FMT(dp[rt][t]) = \sum_{rt_2相邻于 rt_1,t_1+t_2 = t-1} FMT(dp[rt][t_1]) \cdot FMT( dp[rt_2][t_2] )$

$dq[S] = FMT(dp)[][][S]$

本来的问题是 ，前两维正常转移，第三维卷积，有了 dq 就是第一维点积，后两维正常转移。

枚举$S$考虑$dq[S]$，它的转移就是

记录$f[][] = dp[S][][]$

$f[rt][t] = \sum_{T\in R(S)\cap N(rt)} \sum_{t_1+t_2=t-1} f[rt][t_1] \times f[rt][t_2]$

。。。掉线

最后空间$n^2$时间$2^n nm$

---

容斥的优势： 直观 劣势：需要严格的定义 Branching Walk

卷积优势： 不需要额外定义，劣势：整体算法比较抽象

---

为什么可以压空间？

因为这个问题具有比较强的局部性，可以发现$S$这个维度是比较自由的，只要或起来是$S$就可以了。

为什么原来的染色数不能压？因为不太可以求初值。转移过程是可以压到多项式的。