此间最是少年忆难断

· · 算法·理论

生成子图划分及容斥问题

前言：

本文写了一大半，然后作者很遗憾打银退役了，虽然没有补完，但是对于入门完全足够了

大家如果有推荐的题欢迎发给我。

抓出来有提交地址的题

图上一些状压&子集幂级数&容斥专题，难度基本上递增，写的一般很详细，非常适合没学过的新手入坑（宝宝的集合类状压dp启蒙题？？），难度循序渐进，从简单问题类比到困难问题，后几道题难度对于新手较大。

极少部分题目想要通过可能需要子集卷积和子集幂级数的一些知识，但是这并不是重点，我认为能够对此类问题进行划分与容斥就已经掌握了知识的核心，子集幂级数操作不过是个板子，晚点学也不迟，本文也基本上不会用到生成函数知识，ln 和 exp 也是通过组合意义与枚举子集来介绍的。

笔者水平不高，这也是笔者第一次写较大体量的题解文章。如有笔误&知识错误还请麻烦指出，错别字可能有点多但是应该不咋影响阅读。

一些声明：

导出子图：选一些边和它们的端点构成点集。

生成子图：选一些点和两端都在它们内的边集。

SPS：集合幂级数，不理解生成函数的话可以理解为一个状压 dp 数组即可，如集合幂计数 f(x) f(x)=\sum F(S)x^{S}，指数上是一个集合，不同集合对应的不同的 x指数的一个多项式。

为防止歧义，本文使用 ISO-80000-2 中的要求：用 \subseteq 表示子集，\subset 表示真子集，请注意区分。

前置知识：常见生成子图类的问题划分

例：拓扑序计数

考虑统计 F(S) 表示 S 点集的拓扑序的数量，通过枚举其最后一个加入的点 u，若 u 不存在到 S - u 的边，则可以考虑合法的子拓扑序 u, F(S-u)，故 F(S)=\sum_{u\in S,out(u) \cap S=\varnothing} F(S-u)。

例：独立集划分计数

这是一个较为经典的 NPC 问题，求将图划分为若干个独立集的方案数。

考虑统计 G(S) 表示 S 点集的独立集划分数，考虑枚举一个独立集划分出去，但是这样会导致 \{A,B\} 先划分出 A 和先划分出 B 会算重，于是我们钦定划分出一个点 u 所在的独立集，于是我们有

G(S)=\sum_{u\in T,T\subseteq S,\text{T 是独立集}} G(S-T)

常见的做法是令 u 为 S 中最小的元素，方便使用 lowbit，直接枚举子集做复杂度 O(3^n)。

这其实是子集幂级数的 exp，其意义对应着非空集合构成集族的方案数，使用子集幂级数知识可以做到 O(2^n n^2)，在此不叙述。

由此引出下文 “exp” 指 由 f(S) 集合内部方案数 推出 G(S) 集族构成方案数，可以理解为“拼”，其计算方式和我们上面讨论的相同，有

G(S)=\sum_{u\in T,T\subseteq S} F(T)G(S-T)

例：连通生成子图计数

这是另一个经典的 NPC 问题，求一个图联通的生成子图个数。

考虑枚举子集 S，求出每个子集生成子图计数：2^{e(S)}，对于大小为 1 的集合来说，所有生成子图都是联通的 F(S)=1，我们依次递推出更大集合的 F(S)，单步容斥，用 G(S) 减去所有不连通的方案数，类似上方的我们枚举某个点 u 所在的连通块 T，那么 T 是一个连通子图，剩下部分 S-T 是生成子图，有

F(S)=2^{e(S)} - \sum_{u\in T,T\subset S} F(T)2^{e(S-T)}

常见的做法是令 u 为 S 中最小的元素，方便使用 lowbit，直接枚举子集做复杂度 O(3^n)。

这其实是子集幂级数的 ln，其意义对应着非空集合构成集族的方案数倒退非空集合构成的方案数，使用子集幂级数知识可以做到 O(2^n n^2)，在此不叙述。

由此引出下文 “ln” 指 由 G(S) 集族构成方案数 推出 F(S) 集合内部方案数，可以理解为“拆”，其计算方式和我们上面讨论的相同，有

F(S)=G(S) - \sum_{u\in T,T\subset S} F(T)G(S-T)

例：生成树与生成森林计数*

开始增大难度了。

考虑树应该如何归约到子图的生成树：拿出一个点 u，剩下部分分裂为若干个连通块，每个连通块都是其对应点集的生成树，为了不算重我们钦定拿出目前标号最大的这个点。

从小到大枚举点 u，维护目前的 f(S) 表示 S 的生成树计数，考虑加入一个点 u，其连接了若干子树，即若干不同连通块（无序的） T_1\dots T_k，其分别有向 u 连边 c_1\dots c_k 条，那么这样的生成树的棵树就有 \prod f(T_i)c_i 棵，转移到 \bigcup_{i=1}^{k} T_i\cup \{u\}，所以我们关心对于每个点集 S 划分成若干连通块，每个连通块向 u 连一条边的方案数，我们称之为 G(S)。

于是现在对所有点集的 f(S) 乘上 S 和 u 的边数，然后现在变成了 “已知内部方案数的若干集合的无序组合” 成为集族，这是一个“拼”的关系，和前面一样，有

G(S)=\sum_{x\in T,T\subseteq S} F(T)G(S-T)

于是我们就求出了加入 u 后含 u 的点集的的生成树计数，依次加入每个点，即可求出答案。

直接做时间复杂度 O(\sum_{i=1}^n 3^n)=O(3^n)，使用子集 exp 时间复杂度 O(2^nn^2)，该使用增量法维护子集幂级数的方法被称为“逐点牛顿迭代法”。

而生成森林的数量，就是生成树集合构成的集族，关系也是“拼”。直接子集 exp 即可。

提交地址：https://www.luogu.com.cn/problem/AT_abc253_h （这个题需要多记录一个边数，但基本上就是板子）

*: 什么，你问我为什么不用矩阵树定理？首先这是图上状压问题的专题，而这是一个有启发性的做法，其次如果要求每个点集的生成子图计数的话，这个做法是更加优秀（2^n n^2），并且它可以维护生成树的特殊信息，而不仅是边权乘积。

例：生成仙人掌计数与荒漠计数

我们先来考虑生成环的计数法，枚举每个环上某个起点 u，选择在环上编号最大的点 u 作为起点，仅因此仅考虑编号为 [1,u] 的点构成的环，令 f_{S,i} 表示点集为 S 停留在 i 的路径数，可以找出 S 构成的环数，这部分时间复杂度 \sum_{i=1}^n O(2^i i^2)=O(2^n n^2)。

接下来的过程与生成树计数类似，只是“点”可以是“点集”了。

类似上方。逐个加入 u，逐集枚举含 u 的 S 即可（需要钦定 S 中包含了目前标号最大的点），然后就变成每个连通块可以向 S 连一条边，将所有不含 S 的集合拿出来，乘上对应边数后和上面完全一样，进行子集 exp 即可求出无序选择若干连通块并向 S 连边的方案数，用于更新点集 S 的生成仙人掌计数。

直接做时间复杂度是 O(4^n) 的：枚举集合 S，对不含 S 的集合的集合幂级数做 exp（“拼”），可以使用子集 exp 操作优化至 O(3^n n^2)，在后文会介绍一种更优秀的做法。

生成荒漠计数是简单的，这和生成仙人掌之间也是“无序，拼”的关系，直接子集 exp 即可。

提交地址：https://codeforces.com/gym/102331/problem/C

例：生成连通欧拉子图计数

求图 G 有多少个生成子图有欧拉回路，考虑先统计生成的欧拉图，每个点的度数都为偶数，将一条边视作一个二进制下有且仅有两个 1 的数，然后即求选择若干数异或起来为 0 的方案数，这个可以使用线性基：插入失败的数字无论是否选择总是可以使得插入成功的数有唯一的方式把它异或成 0。

接下来我们的问题就是知道了每个点集不一定连通的方案数，要求每个点集连通的方案数，不连通点集和点集之间是集合无序组成集族的关系，而我们已知集族方案数 G(S)，所以是“拆”的关系，有

F(S)=G(S) - \sum_{u\in T,T\subset S} F(T)G(S-T)

即子集 ln。

直接做时间复杂度 O(3^n+2^n m)，用低复杂度的子集幂级数操作可以做到 O(2^n(n^2+m))。

即这类问题往往是知道连通求任意，或知道任意求连通，其分别对应着其 SPS 的 ln 与 exp。

提交地址：https://loj.ac/p/6673

例：点双连通生成子图计数

本部分略难，看不懂跳过直接阅读容斥部分不影响后续阅读。

点双连通图的特征是没有割点，我们通过钦定编号最小的割点来单步容斥。

我们让 F_i(S) 表示“S 的连通生成子图中割点标号都 \leq i” 的图计数，那么答案即 F_(n)，我们先求连通图计数 F_0(S)，像上面提到的那样将生成子图计数“拆”回连通计数：直接进行 ln 即可。

接下来考虑用 F_{i-1} 计算 F_{i}，即 i 为割点，考虑所有包含 i 的集合 S，将 i 删除后会留下若干个连通块和若干连通块连接向 i 的边，这些连通块之间是独立的，我们要求删去后仅有一个连通块的方案数。

考虑若删去后形成了多个连通块的情况，其恰好对应由若干个“单个连通块和连边”任意无序组成的，所以我们已知“若干个[连通块及一些连边]”构成的 SPS，要求“恰好一个[连通块及一些连边]”的 SPS，就是“拆”的关系。

对于所有含 i 的集合 S 的 F(S)，令 G(S)=F(S-i)，对 G 取 ln 即可得出“恰好一个去掉 i 之后的连通块和一些到 i 的边”的SPS，

这个逐点进行单步容斥的过程被称为“点双连通变换”，时间复杂度 O(3^n n) 或 O(2^nn^3) 或 O(2^n n^2\log n)，常数似乎不大，有很多减少常数的办法，正常写法基本上 n=20 都只要 3~4s，卡下常数能到 1s。

提交地址：https://loj.ac/p/6729

例：边双连通生成子图计数

本部分很难，看不懂跳过直接阅读容斥部分不影响后续阅读。

声明：该做法非常绝妙且神秘，在这里主要给出解释与感性理解方式，处于证明意义不大就先放掉了。

考虑“边”在生成子图/集合幂级数中并不是一个可以直接被描述的“对象”，于是只能考虑将“基于边”转化为“基于点”的：发现割边是一个大小为 2 的点双连通分量，且大小为 2 的点双连通图一定是割边。即我们要求“不含大小为 2 的点双连通分量”的连通的生成子图个数。

考虑点双连通变换 G=\text{Trans}(F) 是将生成连通图的 SPS F(S) 转化为生成点双的SPS G(S)，那么点双连通变换的逆变换 F=\text{Trans}^{-1}(G) 就是将生成点双的 SPS 转化连通图的 SPS。

于是我们考虑将“点双连通分量的 SPS G”换成“除了大小为 2 的点双连通分量的SPS G'”，再做点双连通逆变换 F'=Trans^{-1}(G')，就得到了“不含大小为 2 的点双连通分量的连通生成子图” 的 SPS 了，即是边双的 SPS。

这个 \text{Trans}^{-1} 怎么做呢？直接将点双连通变换中的 ln（拆）都换成 exp（拼）即可，这和 \text{Trans} 恰好每步都是是逆变换。

如何理解这个 \text{Trans}^{-1} 的意义？除了从逆变换的角度还可以考虑顺次枚举每个点 i 并 exp 包含 i 的集合的意义：枚举割点 i，由割点编号小于 i 的情况，用若干个用割点更大的部分在 i 周围拼起来起来。

一些较为经典的容斥问题

ABC236H

题意：

给出 n,m,(D_1\dots D_n)，问有多少序列 (A_1\dots A_n) 满足 A_i 都是 [1,M] 互不相同的正整数，且 A_i=K_i D_i(K_i\in \mathbb N+)，对 998244353 取模。

### 做法： 考虑容斥掉互不相同，钦定若干组相等关系并将其考虑为边，若钦定了 $E$ 中的相等关系必须成立的方案数为 $P(E)$，那么答案为 $\sum (-1)^{|E|} P(E)$，但是考虑到钦定 $E$ 中的边集实际产生的相等关系仅和 $E$ 产生的连通性相关，每个连通块的限制是连通块的 $A_i$ 的最小值，于是考虑基于点集的连通性来统计边集及其对应的方案数。 最终图中的若干个连通块，任意无序“拼”成了最终的图，故我们考虑求出每个点集 $S$ 作为连通块的容斥系数，再通过 exp 拼出任意图的容斥系数，即答案。 考虑一个被钦定相等的连通块 $S$ 的容斥系数 $\sum (-1)^{|E|}$，即用奇数条边连通 $S$ 的方案数减去用偶数条边连通 $S$ 的方案数。这个只和集合点数相关的系数（称为 $h(x)$）。 我们依然考虑使用单步容斥，钦定 $S$ 中编号最小的点 $u$ 所在的连通块（在这里我们只在乎大小），用 “不要求连通性的容斥系数之和” 减去一个包含 $u$ 的连通块 $T$，乘上 $S-T$ 的 “不要求连通性的容斥系数之和”。注意到 “不要求连通性的容斥系数之和” 等于 $[n=1]$，即选奇数条边和偶数条边的方案数在存在边的情况下总是相同的，因此剩下的部分的 “不要求连通性的容斥系数之和” 仅在 $S-T$ 的大小为 $1$ 时非零，故仅用考虑 $|S-T|=1$ 的情况，即任选一个不为 $u$ 的点留下，拿出的连通块的的容斥系数为 $h(x-1)$， $h(x)=-(x-1) \times h(x-1)$。 于是我们对每个点集求出其最小值及容斥系数，将其 SPS 用 exp 拼起来即可得互不相同的答案的 SPS 了。 ## [P6846](https://www.luogu.com.cn/problem/P6846) ### 题意： 给出 $n$ 个点 $m$ 条边的有向图 $G$，你可以翻转 $G$ 中的边，使得 $G'$ 成为一个 DAG，对所有可能达到的 $G'$，求需要翻转的边数的和，对 $998244353$ 取模。 $n\leq 18,m\leq \frac {n(n+1)}2$，3s 1G。 ### 做法 考虑一个 DAG 与其反图 DAG 一一对应，且任意一个图到他俩的需要反转的边数之和为 $m$，故我们只需要统计将 $G$ 看作无向图并定向为为 DAG 的方案数再乘上 $\frac m 2$ 即可。 （其实没想到这个也能做？） 令 $F(S)$ 表示点集 $S$ 被定向为 DAG 的方案数，考虑通过在一个子 DAG $S-T$ 的基础上加一层度数为 $0$ 的源点 $T$ 来得到 $S$ 中的某个 DAG，要求 $T$ 得是原图的一个独立集（否则 $T$ 中的点显然有先后关系，不可能是原图的一些源点），但是我们只能钦定 $T$ 中的点是源点，不能保证 $S-T$ 中的点不是源点。 令 $A(T)$ 表示恰好 $T$ 中的点是源点的方案数，难以直接求出，于是令 $B(T)$ 表示 $T$ 中的点被钦定为源点的方案数这是容易求出的：考虑钦定 $T$ 中的点为源点，要求 $T$ 是独立集，此时 $T\to S-R$ 的边方向均为源点到 $S-T$，剩下部分是一个任意的 DAG，方案数为 $F(S-T)$。 关系如下： $$ B(T)=F(S-T) $$ $$ B(T) =\sum_{T\subseteq R} A(R) $$ 子集反演得 $$ A(T) = \sum_{T\subseteq R} B(R) (-1)^{|R-T|} $$ 对于每个 $S$ 的非空子集我们要求所有恰好的方案数之和，即使用 $B$ 表示出 $F(S)$。 （第三行是交换求和顺序，统计每个 $B(R)$ 的系数） $$ \begin{aligned} f(S)=&\sum_{T\subseteq S,T\neq \varnothing} A(T)\\ =&\sum_{T\subseteq R \subset S , T\neq \varnothing} B(R) (-1)^{|R-T|}\\ =&\sum_{R\subseteq S,R\neq \varnothing} B(R)\sum_{T\subseteq R,T\neq \varnothing} (-1)^{|R-T|}\\ =&\sum_{R\subseteq S,R\neq \varnothing} B(R) (-1)^{|R|+1} \end{aligned} $$ 于是我们就有了这样的转移！ 所以 $$ F(S) =\sum_{R\subseteq S,\text{R 是独立集},R\neq \varnothing}(-1)^{|R|+1}F(S-R) $$ 枚举子集解决该问题，时间复杂度 $O(3^n)$，可以通过题目。 这个问题的本质其实是若干子集的 $G(R) = (-1)^{|R|+1}[R \text{ 是独立集}]$ 作为系数的“有序排列”，即“排”的关系，直接解决的复杂度是 $O(3^n)$，其对应子集卷积的 seq 操作，其关系为 $$ F(S)=\sum_{T\subseteq S} G(S) F(S-T) $$ 即令 $F=\mathcal{SEQ} (G)=\frac {1}{1-G}$，可以通过集合幂级数求逆 $O(2^nn^2)$ 做掉。 ## [ABC306H](https://atcoder.jp/contests/abc306/tasks/abc306_h) ### 题意： 给出 $n,m,((U_i,V_i)\dots (U_m,V_m))$，你可以给 $A_1\dots A_n$ 随意赋值，若 $A_{U_i} > A_{V_i}$ 则 $B_i='>'$；若 $A_{U_i} = A_{V_i}$ 则 $B_i='='$，若 $A_{U_i} < A_{V_i}$ 则 $B_i='<'$，在任意给 $A_1\dots A_n$ 赋值的基础上可以得到多少个不同的 $B$ 序列？对 $998244353$ 取模。 $n\leq17,m\leq \frac{n(n+1)}{2}$，3s 1G。 ### 做法： 将关系看作边，边可以定有向（正/反）、或无向，那么一组符合条件给关系应该可以描述为“将无向边”构成的连通块内不能有有向边，且将一个无向边连通块缩起来后形成 DAG。 定向、DAG 计数，与上面那个问题是高度相似的，现在问题是可能存在一个点集缩起来成为一个点的情况，考虑继续让 $F(S)$ 表示 $S$ 中的点集缩点并定向成 DAG 的方案数，考虑在接下来的一层钦定若干个 “源点集合” $T$，每个源点集合内部必须用等号连起来，$T$ 中的每个连通块一定是一个源点集合。 我们重新考虑普通 DAG 计数的容斥，根据我们的在上一题的推导，在 $S$ 的前面加一个大小为 $T$ 的点集带来的容斥系数是 $(-1)^{|T|+1}$，现在相当于直接在原来的 DAG 前面放“缩好了的点”，后来连边也是连向“缩好了的点”，所以 $T$ 的容斥系数就是 $G(T)=(-1)^{\text{|T|中的连通块数}+1}$，其他部分与上一题完全一致。 $$ F(S)=\sum_{T\subseteq S} G(T) F(S-T) $$ 可以做到 $O(n^3)$ 或 $O(n^2 2^n)$。 --- 接下来开始可能有一点点 difficulty cap，看不懂的可以选择慢慢思考或者开摆润掉，如果觉得前面很轻松可以试着独立挑战下接下来的问题。 ## [P10104](https://www.luogu.com.cn/problem/P10104) ### 题意： 给出 $n$ 个点 $m$ 条边的无向图 $G$，长度为 $n$ 的上界数组 $(cir_1\dots cir_n)$，以及异或和 $C$，请对满足以下条件的 $(a_1\dots a_n)$ 数组计数。 - $0 \leq a_i \leq cir_i,\forall 1 \leq i \leq n$。 - 对于每条边 $(u, v)$，$a_u \ne a_v$。 - $a_1 \oplus a_2 \oplus \cdots \oplus a_n = C$，其中 $\oplus$ 代表异或。 对 $998244353$ 取模。 $n\leq 15,m\leq\frac {n(n-1)}{2}$，4s 1G。 - 部分分 $m=0$。 - 部分分 $n\leq 13$。 ### 做法： 我们先来考虑 $m=0$ 的问题，虽然这个和主题关系不大，即求若干个限制 $a_i\leq u_i$ 的数字异或起来恰好为 $C$ 的方案数，我们若考虑数位 dp，需要从高位开始、记录高位匹配，记录 $state$ 表示哪些数在高位仍然顶满了 $cir_i$ 的限制的方案数，这样复杂度较高，虽然可以通过这个部分分，但是处于后面的使用我们还需要优化： 注意到若 $state$ 中存在没有顶满高位限制的数，则接下来它可以在 $[0,2^i)$ 中任意选择，也就是说，其它位可以开摆了！无论其他位置如何选择，$i$ 总是存在唯一选择把后面剩下的位异或成 $C$，于是我们可以枚举第一个出现不满的位置，在每位可能需要进行一个 $O(n)$ 的 dp（用于钦定第一个），可以 $O(n\log w)$ 地解决“若干个 $a_i\leq cir_i$ 异或起来为 $0$” 的方案数，。 现在问题回到解决“互不相同”上。 在做过上面的 P6846 后，你应该知道我们该做什么：把这个“互不相同”容斥成“钦定相同”，钦定边集 $E$ 中的相同，我们仍然只关心 $E$ 构成的连通块，每个连通块内部的值相同，其限制均为最小，不同连通块之间独立（等价于 $m=0$ 的问题），且一个奇数大小的连通块的异或和为 $a_i\leq cir_i$，偶数大小的连通块的异或和总为 $0$。 考虑让 $G(S)$ 表示连通块 $S$ 的容斥系数，选边集 $E$ 连通 $S$ 的 $\sum (-1)^{|E|}$，不要求连通的容斥系数之和为选偶数条边和奇数条边的差，在 $E(S)\neq 0$ 时总为 $0$。依然考虑采用单步容斥的方法求出容斥系数，用连通的减去钦定某个点所在的连通块和剩下部分不连通的系数。 $G(S)=[|E(S)|=0]-\sum_{T\neq \varnothing ,T\subseteq S} G(T) [E(S-T)=0]$。 这个“连通-不连通”的关系仍然是“连通由若干不连通任意无序组成”，其关系为 “拆” 即子集 ln，于是我们可以求出每个点集的容斥系数。 接下来考虑等价关系划分后的问题，我们只关心最终哪些点成为了奇数大小连通块的最小值，然后分别解决这些 $m=0$ 的问题。 令 $F(S_1,S_2)$ 表示目前已经考虑了点集 $S_1$，其中 $S_2$ 中的点作为某个奇数大小连通块的方案数，那么有 $$ F(S_1,S_2) =\sum_{T\in S_1,\left|T\right|\bmod 2 =1,u=\min (T),u\in S_2} F(S_1-T,S_2-\{u\})G(T)+\sum_{T\in S_1,\left|T\right|\bmod 2 =0,u=\min (T)} F(S_1-T,S_2) (cir_v+1) $$ 令 $U$ 全集，答案即所有 $F(U,S)$ 对应的 $m=0$ 的问题的答案乘上对应系数之和。 于是我们现在在 $O(4^n+2^n\log w)$ 的时间复杂度内解决了问题，可以通过 $n\leq 13$，其实适当剪枝也可以冲过 $n\leq 15$（因为仅有奇数大小连通块的最小值才有用能够减少很多状态），采用子集幂级数相关科技也难以降低复杂度，考虑从“最小值”这个角度优化。 类似轮廓线 dp，按 $a_u$ 从小到大枚举 $u$，每次若干加入 $u$ 作为最小值的集合，此时我们一定不会再加入 $[1,u)$ 中的点，因此我们不再关心 $[1,u)$ 是否在 $S_1$ 中，只关心是否在 $S_2$ 中，于是我们只需要记录 $\leq u$ 的点是否在 $S_2$ 中，和 $>u$ 的点是否在 $S_1$ 中，（显然它们就算在 $S_1$ 中也不可能是最小值在 $S_2$ 中），于是我们直接记录每个点是否在对应的集合中即可，枚举子集转移，时间复杂度 $O(3^n n+2^n \log w)$。 这似乎也算一种逐点牛顿迭代。 ## [P10221](https://www.luogu.com.cn/problem/P10221) ### 题意： 难以形式化（？。 现在有若干事件，若干事件按某顺序发生称为时间段，现在 $n$ 个事件，事件的发生间有依赖关系构成一 DAG $G$，要求 $u\to v$ 则 $v$ 必须在 $u$ 发生后发生。 原本有一个随机时间段（不一定合法，事件发生是等概率随机排列）。 现在出现了一个小 A，小 A 随机对时间段切了 $K$ 刀，第 $i$ 刀会在由时间段和刀切入的位置构成的长度为 $n+i-1$ 的序列中随机选择一个间隙或开头结尾，插入一个切断点。 现在时间段被劈开成了 $K+1$ 段，求对于所有随机的时间段和小 $A$ 随机的切法，请问小 B 存在一种重排 $K+1$ 段时间得到合法的时间段的概率。 $n\leq 15,m\leq \frac {n(n-1)}{2},k\leq n$， 1.5s 1G。 - 部分分 $n\leq 13$。 ~~感觉这个题很典啊，为什么这么多人省选不会做，我要嘲笑你们~~ 分成三个部分：时间段内事件顺序，时间段之间合法性，对原序列以及切法计数 --- 时间段内事件顺序 即考虑 $k=0$ 的情况，求有多少个排列满足事件的先后关系，即对事件依赖关系的图进行拓扑序计数。 --- 时间段之间合法性 接下来考虑 $k\neq 0$ 的情况：存在若干段时间，每段时间内塞了一个事件的点集，然后时间段之间的依赖关系**必须构成一个 DAG**，（若出现环显然不存在一个合法的重排顺序，即拓扑序），于是我们即要将事件划分到时间段内，使得时间段之间的边构成 DAG，注意到这是一个形如 DAG 计数的问题。 --- 对原序列以及切法计数 考虑将事件划分成了若干非空集合 $S_1\dots S_i$，以及 $k+1-i$ 个空集，则我们将原序列切若干刀切成这种情况的方案数为： $$ \binom {k+1}{i} i! k! $$ 分别表示选取非空段的位置并排列，特殊化空寂因为空集之间的顺序是不重要的。 $k!$ 表示按任意顺序排列 $k$ 刀切的顺序。 --- 于是我们需要求出每种事件的划分，使得集合之间的关系是 DAG，划分内部的权值为内部的拓扑序数，预处理 $Topo(S)$ 表示 $S$ 的拓扑序数，并且我们还关心划分的非空集合数。我们先不考虑非空集合，稍后再考虑。 考虑使用一个 DAG 计数的容斥方式来统计：每次加入 DAG 一层的点，然后根据加入的点数 $|T|$ 会带来一个容斥系数 $(-1)^{|T|}$。 和上面的 ABC306H 类似，我们现在可能使用一些点集作为 DAG 中的一个点，其权值为拓扑序数，于是我们加入一层点的可能性变得多起来了，于是我们可以先预处理 $Compo(S)$ 表示 $S$ 集合作为拓扑序中一层的容斥系数之和，由若干 $S_1\dots S_k$ 无序构成，且要求 $S_i$ 之间没有边，否则它们不能在同一层。 容斥系数为 $(-1)^{k+1}\prod Topo(S_i)$，为方便转移记录 $R(S)=-Compo(S)$，把 $-1$ 拆分到每一步乘。 $$ R(S)=\sum_{u\in T,e(T,S)=e(S,T)=0} - R(S-T) Topo(T) $$ 接下来再使用我们算好的容斥系数进行的 DAG 容斥，一层一层加入点，让 $F(S)$ 表示。 很遗憾 暂时没时间写了。建议去看 Luogu 题解吧。 ## [Uoj37/强连通生成子图计数](https://uoj.ac/problem/37) ### 题意： 给出 $n$ 个点 $m$ 条边的有向图 $G$，问 $G$ 有多少生成子图是强连通的。 $n\leq 15,m\leq n(n-1)$，1s 256M。 短小精悍。 这个问题看着非常不可作，于是正难则反，考虑不是强连通子图的个数： 不是强连通子图的图一定在缩点后会形成DAG，而将图删边/定向成为 DAG 是一个较为经典的容斥问题。 我们考虑该图缩点后形成了若干个点的 DAG，那么枚举 DAG 的源点层即可转移到一个互不连边的集合（有向图好像不能叫独立集？）和另一个 DAG 的情况，但是钦定了 DAG 的源点层并不能保证剩下的图的所有点一定都不是源点，所以考虑一个经典的容斥。 （我们很好求“钦定某一层源点”的方案数，并希望以此求出“恰好某一层源点”的方案数） 下面这段内容的定义均为 **缩点后** 的 **DAG** 上。 令 $U(S)$ 表示钦定子集 $S$ 是源点层的方案数，$V(S)$ 是恰好集合 $S$ 中的点为源点层的方案数，$F(S)$ 表示 $S$ 构成缩点后的非孤点 DAG 方案数。 根据定义有这些关系：（第三个是第二个的子集反演） $$ F(S) =\sum_{T\subseteq S,T\neq\varnothing}V(T) $$ $$ \begin{aligned} U(S) &= \sum_{S\subseteq T,S\neq\varnothing}V(T) \\ V(S) &= \sum_{S\subseteq T,S\neq\varnothing}(-1)^{|S|-|T|}U(T) \end{aligned} $$ 注意 空集是不能取的！。 $$ \begin{aligned} F(S) &= \sum_{T\subseteq S,T\neq\varnothing} \sum_{T\subseteq R} (-1)^{|T|-|R|} V(R) \\ &= \sum_{R\subseteq S,R\neq \varnothing}(-1)^{|R|} \sum_{T\subseteq R,T\neq \varnothing} (-1)^{|T|}V(R) \\ &= \sum_{R\subseteq S,R\neq \varnothing}(-1)^{|R|+1} V(R) \end{aligned} $$ 这个容斥就是前面“DAG计数”中的转移。 让我们回到对原图的强连通方案计数： 现在我们转移出的方案数是之和**这一层钦定的**强连通分量数量相关，更进一步地，或者说，之和强连通个数的奇偶相关。 所以我们需要求原图中某些子集划分成奇数个，或者偶数个强连通分量的方案数，不如直接点，求容斥系数之和，因为将 $-1$ 的系数分摊到每一个强连通分量上。 $f(S)$ 继续表示 $S$ 构成一个缩点后非孤点的 $DAG$ 的方案数， $g(S)$ 表示集合 $S$ 的容斥系数之和（奇数个强连通、偶数个强连通的方案数的差），$h(S)$ 表示集合 $S$ 是一个强连通分量的方案数，可以用 $f(S)$ 直接得出。 注意我们原本求出的 $g(S)$ 对于目前的 $S$ 是不包含把整个图当作一个强连通分量的而 $g(S)$ 对于目前的 $f(S)$ 的系数显然是 1，代入上面的式子就能求出这个图至少两个强连通分量的方案数以求出 $f(S)$。 所以有： $$ g(S)=\sum_{T\subset S,u\in T} -h(T)g(S/T) $$ $$ f(S)=\sum_{T\subseteq S,T\neq\varnothing}-g(T)\times (2^{E(S/T)+E(T\to S/T)}) \\ h(S)=2^{E(S)} - f(S) $$ $$ g'(S)\gets g(S)-h(S) $$ 时间复杂度 $O(3^n)$ ，因为涉及到指数上的边集大小，所以 【我感觉，应该是，大概也许】没有 $O(2^n\text{poly}(n))$ 集合幂级数的复杂度了吧，如果有神仙会的话欢迎和我讨论。 --- # 图上点集划分与集合幂级数的杂题与智慧收录（杂题） ## [P4221](https://www.luogu.com.cn/problem/P4221) 【题解待补】 ## [CF1842H](https://www.luogu.com.cn/problem/CF1842H) 【题解待补】 ## [QOJ2068](https://qoj.ac/problem/2068) 【题解待补】 ## [loj6719](https://loj.ac/p/6719) 【题解待补】