目前是半成品，太晚了就没写了。
前置-子集反演
令 \(f_S\) 表示恰好满足限制集 \(S\) 下的答案，\(g_S\) 表示至多满足限制集 \(S\) 下的答案。（满足 \(S\) 的一些，但是不能满足 \(S\) 之外的）。
我们对此有结论：
\(f_S=\sum_{T \subseteq S} (-1)^{|S|-|T|}g_T\)
推导：
首先有 \(g_S=\sum_{T \subseteq S}f_T\)。
\(f_S=\sum_{T \subseteq S} (-1)^{|S|-|T|}g_T=\sum_{T \subseteq S}(-1)^{|S|-|T|}\sum_{Q \subseteq T \subseteq S} f_Q=\sum_{Q \subseteq S} f_Q\sum_{Q \subseteq T \subseteq S} (-1)^{|S|-|T|}=\sum_{Q \subseteq S} f_Q\sum_{T \subseteq S-Q} (-1)^{|S|-|Q|-|T|}=\sum_{Q \subseteq S}f_Qh_{S-Q}\)
令 \(h_S=\sum_{T \subseteq S} (-1)^{|S|-|T|}=\sum_{i=0}^{|S|} C(|S|,i)(-1)^{|S|-i}=[S=\emptyset]\)。
故 \(\sum_{Q \subseteq S}f_Qh_{S-Q}=f_S\)，即式子成立。
同理如果令 \(g_S\) 表示至少满足限制集 \(S\) 的答案。（可以满足其它的，但 \(S\) 内的限制必须满足）
我们有类似的：
\(f_S=\sum_{S \subseteq T} (-1)^{|T|-|S|}g_T\)
如何证明？我们把上面的 \(g\) 取补集即可得到。
P6442
给定 \(n\) 个全集（长度为 \(m\)）的子集，求选出一些子集使得并为全集的方案数。
\(n \leq 10^6,m \leq 20\)
我们需要求恰好是全集的方案数，子集反演变成求每个子集的 “至少”，令当前要计算的集合为 \(T\)。那么就是要求最后的并是 \(T\) 的子集的方案数。相当于选择的每个子集都是 \(T\) 的子集，因此直接 sosdp 统计一下每个 \(T\) 子集内有多少个给定的集合即可。
P3349
给定一个树和一张图，求排列 \(P\) 的数量满足对于树上一条边 \((x,y)\) 在图上都有对应的 \((P_x,P_y)\)。
\(n \leq 17,m \leq \frac{n(n-1)}{2}\)
转完以后对于一个 \(T\)，是要求所有的 \(P_i \in T\) 时的答案，我们令 \(f_{i,j}\) 表示 \(P_i=j\) 的情况下子树内的答案。转移是朴素的。
形态的刻画
这里一般我们尝试刻画成可以规约的形式，方便我们做 dp。再不行的话把它转化成可计数的经典形式。下面是一些经典的刻画。
tips: 增量的优势是简化了问题，劣势是对于一个相同的图可能会被扩展到多次，没法直接用来做计数。
有向图：
DAG：
规约：把入度为 0 的点从一个
DAG中删掉（删除点以及相连的边），剩下的图还是一个DAG。增量：每次在原有的一个
DAG上，新拿出来一些点，并和原图的入度为0的点连一些指向这些0度点的边，重复这个过程（其实在实际运用的时候我们只需要扩展一步）。
强连通：
增量：对于原有的强连通的图，选择一对 \((u,v)\) 添加一条 \(u\) 到 \(v\) 的路径（如果 \(u=v\) 那么要求这一条路径中间经过的点数大于 \(1\)，理由是显然的），同样每次只需要扩展一步。
规约：考虑容斥一步，统计不强连通，等价于缩点后是数量大于 \(1\) 的极大
scc组成的DAG，我们用类似处理DAG的手法解决。
边双：
增量：在原有的边双上加一个路径，不过这里要求必须包含一个其它的点。
不边双连通：缩点后是一棵边双树，那么我们可以类比 dag 的方法枚举叶子（这里你得限制不是全集）。当然你得考虑一条边连着两个点的情况，这种就全是叶子得考虑进答案里
点双：在点双上不断加一个链，不过这里要求起点终点不一样（\(u \ne v\)）。
例题
DAG/非scc
我们令 \(f_S\) 表示点集 \(S\) 内部的点和边组成的图为 DAG 的方案数，那么在转移的时候，我们可以枚举入度为 0 的点，那么将这些点以及它们相邻的边删除后，剩下的图应该是还是个 DAG，这样可以规约到子问题：\(f_S=\sum_{T \subseteq S且T非空}f_{S-T} \times ...\)。但这是不对的，因为这里你钦定了一些点是 0 点，意味着一种方.案3在很多种钦定 0 点的选择中会被计算，因此我们想算的恰好满足某些点是 0 点的答案，因此使用子集反演可以得到：\(f_S=\sum_{T \subseteq S且T非空}(-1)^{|T|+1}f_{S-T} \times ...\)。
推导过程大概就是把
bzoj2863
求 \(n\) 个点的有标号
DAG数量。
\(n \leq 10^3\)
板子题。令 \(f_n\) 表示 \(n\) 个点的答案，每次转移枚举入度为 \(0\) 的点的个数即可。
P6846
给定一个 \(n\) 个点 \(m\) 条边的有向图，你可以对每条边选择翻转方向（不能次数>1），求使得图变成
DAG的所有操作方案中操作边数之和。\(n \leq 18,m \leq \frac{n(n-1)}{2}\)
注意到对于一个合法的方案，我们对于把所有边方向取反一下，还是个 \(DAG\) 也是一种方案，并且注意到这样的一对方案操作的边数和为 \(m\)
。于是两两配对之后可以得到答案：\(ans=\frac{m \times c}{2}\)，其中 \(c\) 为方案数。
于是就是套路了，令 \(f_S\) 表示集合内的答案，每次枚举零点的集合 \(T\)，其中 \(T\) 要满足内部没有边，因为只要有边必定存在入度。
AT_abc306_h
有 \(n\) 个数 \(A_1,A_2,\dots,A_n\)，有 \(m\) 条限制形如 \(A_x\)
?\(A_y\)，其中?可以填成<,=,>中的一个。问有多少种填的方法使得没有逻辑上的矛盾？\(n \leq 17,m \leq \frac{n(n-1)}{2}\)。
我们把一个关系看成一条无向边。
如果没有 = 的话相当于给每个边定向使得图是个 DAG，做法和上一个题一致。现在有 = 话意味着我们对于上一个题枚举的 \(T\) 不用要求 \(T\) 内没有边了，我们可以把内部连通的点缩起来（其实就是内部的边全填等于），容斥系数和入度为 0 的点个数相关，这里就是 \(T\) 内缩点完的个数，用并查集维护即可。
uoj37
给定一个 \(n\) 个点 \(m\) 条边的有向图，要求删掉一些边使得图强连通。
\(n \leq 15,m \leq \frac{n(n-1)}{2}\)
考虑令 \(f_S\) 表示集合 S 内部的图（点和内部边组成）强连通的方案数，考虑正难则反，转化为统计不强连通的方案数。不强连通等价于缩点（缩成若干个极大 scc）后是个 DAG，且点数 >1。
于是根据经典套路我们枚举所有入度为 0 的极大 scc 中的点组成的集合，令它为 T。那么我们记 \(g_T\) 表示 \(T\) 内点（就只考虑内部的边）划分为若干入度为 0 的 scc 的方案数。我们可以得到 \(f_S=\sum g[T]*(-1)^{P+1}*2^{edge(T,S-T)+edge(S-T,S-T)}\)，\((-1)^{P+1}\) 是对应的系数，其中 \(P\) 为 \(T\) 中的 scc 个数。
对后面 \(2^k\) 的那个东西的说明：\(edge(T,S-T)+edge(S-T,S-T)\)：T->S-T 中的边不影响 DAG，S-T->S-T 的边因为 T 中已经有个 scc，那么剩下就算只缩成一个，那么点数还是>1，因此S-T内部的边随便连，S-T->T的边是全都要砍掉的，因为入度为 0。
这个不能直接定量。考虑到系数只跟 \(P\) 的奇偶性有关，所以我们可以把 \(g_T\) 定义为奇数个 scc 的方案数 - 偶数个 scc 的方案数。
所以现在就是要求 \(g_T\)，考虑转移。如果单独一个 scc，就是 \(dp_S\)，否则考虑枚举 \(lowbit(S)\) 所在的 scc，那么得到 \(g_T=dp_T-sum(g[S \no T'] \times dp_{T'})\)，其中 \(T'\) 为 \(lowbit(T)\) 所在连通块。这样就做完了。当然有一个细节就是在 \(f_S\) 的转移的时候，\(T=S\) 的时候你不能把 \(dp_S(dp_T)\) 也减掉，因为这个时候你不能把整个划分成一个 scc，这个是合法的。