已经是中年选手了，却没有一个中年选手应有的科技树，这是为什么呢?
实际上我们很久以前就在我的blog见过子集反演这个同志了，那一篇是 一道可能是nowcoder上的题的题解。
但是那个还是太模糊，我们来看一看正统子集题的子集反演。
当然在此之前说明子集反演是什么 : 子集反演用于在 恰好是某个子集 和 在这个子集中钦定/钦定这个子集 之间转换。
现在有满足某种条件的元素集合\(A\)。
设\(f(S)\)表示\(A=S\)的答案，\(g(S)\)表示\(S\subseteq A\)的答案，那么只要这个东西性质不是太差，我们枚举钦定了哪个，应该有\(g(S)=\sum\limits_{T\subseteq S}f(T)\)，此时子集反演给出\(f(S)=\sum\limits_{T\subseteq S}(-1)^{\vert S\vert-\vert T\vert}g(T)\)。
设\(f(S)\)表示\(A=S\)的答案，\(g(S)\)表示\(A\subseteq S\)的答案，那么只要这个东西性质不是太差，我们枚举钦定了哪个，应该有\(g(S)=\sum\limits_{S\subseteq T}f(T)\)，此时子集反演给出\(f(S)=\sum\limits_{S\subseteq T}(-1)^{\vert T\vert-\vert S\vert}g(T)\)。
为什么这是正确的?我不知道，你可以爆力代入\(\sum\limits_{T\subseteq S}(-1)^{\vert T\vert}=[S=\varnothing]\)验证。
ZJOI2016 小星星
给你一个图和一棵树，点数都是\(n\)，求有多少种方案把树重标号，使得它是图的一棵生成树。\(n\leq 17\)。
重标号合法，当且仅当每条边都存在于原图中。
枚举排列没有前途，考虑有什么子结构性质。设\(dp(S,T)\)表示\(S\)重标号变成\(T\)的方案数，然后你发现这个东西是\(4^n\)的所以不行。
呃能不能砍一点?发现树有子结构，可以利用它的局部性砍掉一维，于是我们设\(dp(u,i,S)\)表示\(u\)子树重标号变成\(S\)，其中\(u\)变成\(i\)的方案数，然后考虑转移，我们枚举第一棵子树对应的集合，然而转移复杂度高达\(O(n^2)\)，所以总共是\(O(3^nn^3)\)，我们就完蛋了。
然后你发现这是儿子们的子集卷积，于是可以用\(2^nn^2\)的子集卷积做到\(O(2^nn^5)\)。还是过不去。
如何干掉卷积?
这是这个题最牛逼的地方 : 直接抛弃集合这一维。
这会带来一个大问题 : 我们不能保证映射到的集合是不重的。比方说有两条边\(u\leftrightarrow v,v\leftrightarrow w\)，那么\(u,w\)取一样的标号是可以的。
考虑对 不重 进行容斥，也就是说我们容斥出互不相同的限制。考虑设\(f(u,i,S)\)表示子树内每个点都在\(S\)中随便选一个标号，不要求不重，但是要求取遍了\(S\)的方案数，\(g(u,i,S)\)则把取遍的限制也去掉，这形成了 恰好是这个子集 和 在这个子集中钦定 的关系。那么我们要从\(f\)算\(g\)，就有\(g(u,i,S)=\sum\limits_{T\subseteq S}f(u,i,T)\)，反演得到\(f(u,i,S)=\sum\limits_{T\subseteq S}(-1)^{\vert S\vert-\vert T\vert}g(u,i,T)\)。
答案是\(f(1,...,2^n)\)，现在的问题是如何快速计算\(g\)。你发现这是简单的，只需要枚举一个\(S\)，然后算就行了/jy
dp的复杂度是\(O(n^3)\)，总复杂度就是\(O(2^nn^3)\)，卡一卡就过了。
SHOI2016 黑暗前的幻想乡
怎么又是2016（
给你一个完全图，有\(n-1\)种颜色，每条边可以染成一些颜色，求所有恰好包含\(n-1\)种颜色的生成树个数。两个生成树相同，当且仅当边集和颜色都相同。\(n\leq 17\)。
呃考虑我们钦定一棵生成树之后怎么做，或者钦定一个染色之后怎么做。
钦定一个染色好说，这是一个\(n-1\)元\(n-1\)次的GF，拉插大约\((n-1)^{(n-1)}\)个点，拿矩阵树硬消……fuck myself。
钦定一个生成树之后，我们就需要考虑这个生成树怎么染色，你发现从边向颜色连边，这是一个二分图完美匹配计数，不过这还是没法做。
这个不能重太恶心了!还是把它容斥掉。然后就变成每条边都随便染色了。直接矩阵树定理冲，用和 小星星 相同的做法即可做到\(O(2^n(n^3+n^2\log v))\)。
清华集训2014 主旋律
给一个图，求强连通生成子图个数。\(n\leq 15\)。
必然考虑dp，设\(dp(S)\)表示点集\(S\)的强连通生成子图个数。当然你直接集合幂级数科技我也没办法，不过目前我不知道\(O(2^nn^2)\)类似的做法（
考虑用总的减去不强连通的，也就是缩点之后得到的DAG点数超过\(1\)的。我们搜一种缩点之后每个SCC的情况进行转移(不搜SCC之间的边)，注意到每个SCC都是一个子问题，这个性质非常好(实际上这就是非强连通图的结构，我们只是根据结构设计算法)。
搜缩点之后情况 这个复杂度看起来非常高，不过比起爆搜好的多，它是Bell数\(B(15)=1382958545\)，而直接搜是\(2^{210}>10^{63}\)(还是可以在莉oj 1s冲过去?)，并且Bell数渐进上也确实比\(2^{n(n-1)}\)小的多。
考虑怎么算DAG生成子图。
考虑一个拓扑排序，我们枚举所有入度为\(0\)的SCC删掉，把这些点设为\(T\)，那么\(T\)到\(S-T\)就可以随便连边，而\(T\)内部和\(S-T\)到\(T\)一条也不能连，\(S-T\)是一个DAG。
设\(t(S)\)表示\(S\)的DAG生成子图数，把边界设为每个子集的强连通生成子图个数，可以写出这样的东西 :
\[t(S)=\sum_{T\subseteq S,T\neq\varnothing}2^{c(T,S-T)}t(S-T)\]其中\(c(S,T)\)表示\(S\)到\(T\)的边数，容易\(3^n\)递推，具体做法就是\(c(S,T)=c(S-x,T)+\mathrm{popcnt}(e_x\operatorname{and}T)\)，其中\(e_x\)是\(x\)的出边指向的集合。
但是这个是错的，因为我们不能保证我们钦定的就是所有入度为\(0\)的SCC。这形成了 恰好是一个子集 和 钦定这个子集 的关系，于是我们进行子集反演。设\(f(T,S)\)为\(T\)恰好是\(S\)中所有入度为\(0\)的点的方案数，\(g(T,S)=2^{c(T,S-T)}t(S-T)\)为钦定了\(T\)是的方案数，那么有\(g(T,S)=\sum\limits_{T\subseteq R\subseteq S}f(R,S)\)，于是\(f(T,S)=\sum\limits_{T\subseteq R\subseteq S}(-1)^{\vert R\vert-\vert T\vert}g(R,S)\)。\(g\)显然可以在\(O(3^n)\)预处理之后\(O(1)\)计算。
直接把这个代进去，我们得到一个看起来正确了的式子
\[t(S)=\sum_{T\subseteq S,T\neq\varnothing}\sum_{T\subseteq R\subseteq S}(-1)^{\vert R\vert-\vert T\vert}g(R,S)\]这个式子有两个\(\sum\)，看起来不像很能算，考虑化简一下。换个求和号，然后使用著名恒等式\(\sum\limits_{T\subseteq S}(-1)^{\vert T\vert}=[S=\varnothing]\) :
\[\begin{aligned} &\sum_{T\subseteq S,T\neq\varnothing}\sum_{T\subseteq R\subseteq S}(-1)^{\vert R\vert-\vert T\vert}g(R,S)\\ =&\sum_{R\subseteq S}(-1)^{\vert R\vert}g(R,S)\sum_{T\subseteq R\subseteq S,T\neq\varnothing}(-1)^{\vert T\vert}\\ =&\sum_{R\subseteq S}(-1)^{\vert R\vert}-[R\neq\varnothing]g(R,S)\\ =&\sum_{R\subseteq S,R\neq\varnothing}(-1)^{\vert R\vert+1}g(R,S) \end{aligned}\]看起来就非常好，现在枚举缩点后每个SCC的情况之后，我们有一个\(3^n\)的转移了。总复杂度可能是\(4^n+2^nBell(n)\)这样的，当然前面那一项比较低阶，不过为了好看还是留着，这是废话。
如何才能抛开这个 枚举缩点后每个SCC的情况?
仔细观察这个式子，你发现它和缩点后的具体情况没有关系，它只关心你枚举的这个子集里面有奇数还是偶数个SCC。所以我们设\(f(S,0/1)\)表示\(S\)的生成子图中SCC个数为奇/偶数，并且SCC之间没有边的方案数，就有转移
\[dp(S)=2^{c(S,S)}-\sum_{T\subseteq S,T\neq\varnothing}(f(T,0)-f(T,1))2^{c(T,S-T)}2^{c(T,S-T)+c(S-T,S-T)}\]然后我们再考虑\(f\)的转移，你发现\(f(...,0)\)的转移就是枚举\(\mathrm{lowbit}\)所在的SCC，用它的\(dp\)卷上剩下的的\(f(...,1)\)。做完了，复杂度是\(O(3^n)\)。