首先考虑 DAG 计数，设 \(f_{s, s'}\) 表示目前确定的点集为 \(s\)，最后一层点为 \(s'\)，因为我 DAG 计数按照拓扑序一定是一层层转移的，你会发现这个状态数是 \(O(4^n)\)，直接爆炸了。
比较神秘的优化是，去掉 \(s'\) 这一维，转移可能有重，我们直接容斥，容斥系数为 \((-1)^{|s|}2^c\)，\(c\) 为两个点集之间的边数，\(s\) 为你新拓展的点集。
我也不会证明，打表吧。
首先考虑 DAG 计数，设 \(f_{s, s'}\) 表示目前确定的点集为 \(s\)，最后一层点为 \(s'\)，因为我 DAG 计数按照拓扑序一定是一层层转移的，你会发现这个状态数是 \(O(4^n)\)，直接爆炸了。
比较神秘的优化是，去掉 \(s'\) 这一维，转移可能有重，我们直接容斥，容斥系数为 \((-1)^{|s|}2^c\)，\(c\) 为两个点集之间的边数，\(s\) 为你新拓展的点集。
我也不会证明，打表吧。