博弈论好题，做完感觉加深了对 SG 函数的理解！
题意：
给定一张 DAG，问该 DAG 的 \(2^m\) 张导出子图中有多少张满足 \(SG[1]=SG[2]\)
注：此为转换后题意
\(n \leq 15\)
考虑推出 SG 的过程，执行一遍拓扑排序，取 \(\operatorname{mex}\)。
按 \(SG\) 函数值把点分层，则一个 \(x\) 层点需要连所有 \(y < x\) 层点各至少一个。
dp 中重要的是找到答案的一个递推式的形式，发现任意合法答案都能用这种子小形式表达出来。
对于 CSPS2022 T3，发现一个合法的连通块是从多点往上到共同 lca 的路径并，据此分开考虑空 / 全部连到 lca 处。
\(n\) 这么小，子集枚举是少不了了。那么需要 \(f_S\) 表示只考虑集合 \(S\) 中的点，且 \(1,2\) \(SG\) 值相同。然后会发现从后往前枚举是行不通了，因为 \(1,2\) 可能连向任意点，需要存任意点的 \(SG\)，于是考虑从后往前，每次批量把 \(SG=0\) 的点加进来。
形式化地，假设现在枚举到 \(S\)，钦定 \(S\) 的子集 \(U\) 的 \(SG=0\)，\(T=S/U\)，则以下条件应当被满足：
- \(1,2\) 属于一个集合
- \(U\) 集合内部不能连边
- \(U \to T\) 任意连边，\(T\) 中任一点与 \(U\) 中有连边
预处理 \(c_{x,S}\) 表示 \(x\) 到 \(S\) 集合连边总数，则第三条件为 \(\displaystyle\prod_{t \in T} (2^{c_{t,U}}-1)\prod_{u \in U} 2^{c_{u,T}}\)。总复杂度 \(O(n 3^n)\)。
部分借鉴于 官方题解
标签：连边,DAG,任意,agc016F,Game,枚举,SG,dp From： https://www.cnblogs.com/purplevine/p/16972571.html