DFSCount
$f_{S,i}$ 表示从点 $i$ 开始遍历完集合 $S$ 的方案数。转移是看删掉 $i$ 之后会分裂成 $k$ 个连通块就乘一个 $k!$，然后每个连通块选一个点开始遍历。$\mathcal O(2^nn^2)$。
DAG 计数
给无向图，定向使得不存在环，求方案数。
$f_S$ 表示集合 $S$ 的答案。转移是枚举入度为 $0$ 的点剥掉。
| 但是会算重，所以一次需要剥掉一个独立集 $T$，系数是 $(-1)^{ | T | +1}$，正确性归纳证明。 |
色多项式
$f(G,x)$ 表示用 $x$ 种颜色对图进行染色的方案数。
无环定向等价于 $(-1)^nP(-1)$（？）
设 $a(G)$ 表示对无向图 $G$ 进行无环定向方案数。$a(G)=a(G-(u,v))+a(G\vert (u,v))$。考虑 $(u,v)$ 这条边，先确定除了他以外的所有边。如果 $(u,v)$ 之间没有可达关系那他贡献是 $2$，否则是 $1$。设没有可达关系为 $X$，有可达关系是 $Y$。
第一种表示去掉 $(u,v)$ 这条边，的意义是 $(u,v)$ 之间有无可达关系都可以。这样是 $X+Y$。第二种表示把 $(u,v)$ 合并起来。这样是 $X$。加起来就是 $2X+Y$，正好是要统计的。
| 而设 $f(G,k)$ 表示 $G$ 的 $k$ 染色方案数，有 $f(G,k)=f(G-(u,v),k)-f(G | (u,v),k)$，就是一个很简单的容斥。然后怎么着归纳一下是不是就好了（反正我不会）。 |
用这个结论可以把这个这个题做的更优秀。记录当前轮廓线上等价关系即可，复杂度是 $\mathcal O(B(\min(n,m))poly(n,m))$。
[ABC306Ex] Balance Scale
现在有相等的情况。还是设 $f_S$ 表示 $S$ 内部方案。不同的是枚举入度为 $0$ 的连通块 $T$ 的时候，$T$ 不是独立集了，是若干个并起来的块，需要处理辅助转移的一点东西。
QOJ7 主旋律
典。
$f_S$ 表示 $S$ 内部强联通方案数。
枚举入度为 $0$ 的强联通分量集合。也是需要什么辅助转移。
[AGC017F] Zigzag
要做 $m$ 次前缀和。每次做前缀和的位置从前向后做，假设做到了位置 $i$，$1$ 表示向右拐，$0$ 表示向左拐。如果这个位置 $S$ 是 $0$ 则可以把 $i$ 后面的第一个 $1$ 移到 $i$ 的位置，如果没有 $1$ 就新建一个 $1$。
P10221 [省选联考 2024] 重塑时光
不怎么好的回忆。
看成是 DAG 上划分若干个连通块，贡献是连通块内部拓扑序乘积。
如果每次暴力拼一个连通块的话，会算重，一种划分方案会被计算“外层拓扑序数量”次。
所以要容斥，还是枚举若干个集合拼起来的集合，一个数组辅助转移即可。
要记录这个集合里有几个连通块，所以两个集合并起来的时候第二维是一个卷积，拉插可以除一个 $n$。
[AGC024F] Simple Subsequence Problem
| 需要从 $S$ 不重不漏的生成其所有子序列。$f_{S,i}$ 表示已经确定了一个 $S[1,i]$，后面未确定的部分是 $S[i+1, | S | ]$。转移类似子序列自动机。 |
QOJ2068 Fast as Ryser
很奇妙的 trick。
考虑把 $2i,2i-1$ 之间连虚边，这样匹配会形成若干个环和链。
| 对于一个链，$f_{S,x}$ 表示当前匹配的对集合是 $S$，当前点 $x$ 没有匹配。枚举一个 $t\notin S$，匹配 $(x,t)$，转移到 $f_{S | 2^{t/2},t^1}$。 |
对于一个环，钦定他的起点是最大的点，然后转移只能向小的转移，最后再和一开始的连在一起即可。
最后需要做一个子集 exp。
CF468E Permanent
不同连通块之间独立。对于每个块其大小 $\leq k+1$。所以一定有一边大小 $\leq (k+1)/2$。对这半边状压。这样是 $\mathcal O(2^\frac{k}{2}k^2)$。
比较离谱啊！假设对左边状压，那一个左边的点如果扫右边的时候后面没有和他的连边的边了，那他就不需要状压了。
所以每次选左边度数最小的点，把它相邻的点放到右边序列的前面，这样会有右边的一个顺序，按照这个顺序 DP 就跑的很快。
数仙人掌
很深刻！先求 $f_S$ 表示 $S$ 形成了一个环的方案数。然后枚举 $i$，把 $i$ 周围所有连通块做一个 exp，这样 $f_{2^n-1}$ 就是答案。
###