当前位置：首页 > news >正文

杂题相关

news 2026/3/26 17:19:52

[CEOI2015] Amusement Park

\(n\) 个点 \(m\) 条边的有向图，无重边无自环无二元环，将某些边改变方向后使得图变为 DAG，求满足这样条件的所有选边方案的选边数量之和。

\(n \le 18, m \le \frac{n(n-1)}{2}\)。

首先做一个小转化：由于将一只 DAG 所有边反转后还是 DAG，所以可以找出这样的 DAG 对，那么问题转化为求能得到的 DAG 的数量 \(c\)，答案即为 \(\dfrac{c}{2}\times m\)。

\(n\) 很小，可以按拓扑序分配 DAG。定义 \(f_S\) 表示用点集 \(S\) 构成 DAG 的方案数。考虑拓扑排序的过程，钦定 \(S\) 中入度为 \(0\) 的点集为 \(T\)，那么就可以确定所有与 \(T\) 直接相连的 \(S\) 集合中的点之间的边，发现钦定后 \(S-T\) 集合构成一个子问题。显然，如果 \(T\) 中的点之间互相有连边，显然是不合法的，因为这条边两端至少有 \(1\) 个点入度不为 \(0\)。而如果 \(T\) 为独立集，是一定合法的。

此时还有一个问题，就是直接算的话 \(T\) 可能并不包含所有入度为 \(0\) 的点，于是直接容斥就好了，这一部分是简单的。（你也可以通过自己繁衍来推）

\[f_S=\sum _{T\subseteq S,T\neq \varnothing} p_Tf_{S-T}(-1)^{|T|+1}\\ \]

\(p_T =[T\) 为独立集\(]\)。

子集枚举做到 \(\mathcal O(3^n)\)，当然你喜欢的话也可以用 FWT 做到 \(\mathcal O(n^22^n)\)，可能会快一些。

[清华集训 2014] 主旋律

给定一张有向图，无重边无自环，求有多少边的子集删去后，有向图是一个强连通图。膜 \(10^9+7\)。

\(n \le 15, m \le n(n-1)\)

前言

强连通图不好刻画，一步容斥转化为有 \(2\) 个以上的强连通分量；相当于缩点之后的 DAG 有不少于 \(2\) 个节点。

根据上一道题，DAG 计数的套路主要在于分层计算，如此划分子问题。但是本题难点不在于 DAG 计数的套路，而是容斥。

定义 \(f_{S}\) 表示将 \(S\) 集合缩为一个强连通分量的选边方案数。记 \(S \to T\) 的边集为 \(e(S,T)\)。设 \(g_T\) 为：「恰将 \(T\) 划分为 \(k\) 个强连通分量的方案数，且 \(k\) 为奇数」减去「恰将 \(T\) 划分为 \(k\) 个强连通分量的方案数，且 \(k\) 为偶数」，这里是将容斥系数揉到定义里去了。

\[f_S = 2^{|e(S,S)|}-\sum_{T \subseteq S} g_T2^{e(T,S-T)+e(S-T,T)} \]

计算 \(g_S\)，考虑随便找个点 \(u \in S\)（比如 lowbit，当然 highbit, midbit, ... 都可以），钦定它处在一个新强连通分量中：

\[g_S = f_S-\sum _{u \in T \subsetneq S}f_T g_{S-T} \]

注意 \(u\) 不是枚举，而是钦定的某个处在 \(S\) 中的点，比如 \(u = \mathrm{lowbit}(S)\)。还有一个需要注意的地方是：若上述 \(f_S\) 转移中的 \(T\) 枚举至 \(S\)，那么此处的 \(g_S\) 肯定是还没有算出来的。但是考虑 DP 定义，此处的 \(g_S\) 不应算上 \(f_S\) 的贡献，否则 \(g_S\) 中算了仅有 \(1\) 个强连通分量，实际上应该是合法方案，却被减去了。可以先将 \(g_S\) 按不算 \(f_S\) 贡献算出，最后再补上就行了。