今天比赛考到了，不会，丢了 100 分。
rk2,380 -> rk15,280
别问为什么 T4 没过，因为不会 T2。
方法一 \(O(3^n)\)
令 \(f_S\) 为子集 \(S\) 内定向得到 DAG 的方案。
\(f_S = \sum\limits_{\emptyset \not= T\subset S, \text{T 为独立集}} (-1)^{|T| - 1}f_{S - T}\)
考虑 DAG 的分解构造过程，可以将其分为出/入度等于 \(0\) 的最大点集，删除/剥离一层继续这样，考虑逆向构造 DAG，但是发现存在重复计数，可以采用容斥，对于非空点集 \(T\)，容斥系数为 \((-1)^{|T| - 1}\)。
关于容斥系数：有机会总结一下。关于本题，设 \(T\) 的计算容斥系数为 \(g(T)\)，而真实容斥系数为 \(1\)，根据计算方式，大的会被每个小的计算一次（有些时候是有关组合数的系数，但这里根据定义和公式是 \(1\) 次），于是有 \(\forall S, \sum\limits_{T\subset S}g(T) = 1\)
可以构造 \(g(T) = (-1)^{|T| - 1}\)
枚举子集复杂度 \(O(3^n)\)。考虑是不是可以 \(O(3^n)\) 求得容斥系数？
方法二 \(O(n^22^n)\)
貌似子集卷积，记得补
标签：subset,系数,待补,容斥,DAG,子集,定向 From： https://www.cnblogs.com/SkyMaths/p/18391432