主旋律
UOJ #37. 【清华集训2014】主旋律 整理--zhengjun
好像没做过 DAG 计数的题。 首先看到数据范围，考虑状压。 方便起见，记 $cnt_{S,T}=\sum\limits_{(u,v)\in E}[u\in S \and v \in T]$。 设 $f_S$ 表示 $S$ 为强连通分量的选边方案数，由于正面很难算。 考虑反面： $$ f_S=2^{ ......
UOJ #37. [清华集训 2014] 主旋律
[UOJ 传送门](https://uoj.ac/problem/37 "UOJ 传送门") 考虑 dp。设 $f_S$ 为点集 $S$ 构成强连通分量的方案数。 容易想到容斥。设 $ed_S$ 为 $S$ 内部连边数，那么 $f_S$ 就是总的方案数 $2^{ed_S}$ 减去构成的不是强连通分量 ......
【容斥、状压dp】主旋律 题解
【清华集训2014】主旋律 题解 神秘题。 题目简述 给你一个有向图 $G=(V,E)$。求有多少 $E$ 的子集 $E'$ 使得新图 $G'=(V,E')$ 是强连通图。 强连通图的定义是任意两点 $u,v$ 均存在 $u\to v,v\to u$ 的路径。 $n\leq 15,m\leq n\t ......
uoj #37. 【清华集训2014】主旋律
考虑原先求的是 SCC 为 1 的方案数，这很困难！因为并没有能够转移到子问题的路径。 不妨考虑容斥，即 SCC 为 1 的方案数=所有方案数-SCC 不为 1 的方案数。 不妨先集合划分出 SCC，然后就变成了，内部的 SCC 子问题（此时因为钦定的 SCC 个数 >1，因此规模一定变小）以及外层 ......