题意
给你一个有 (n) 个点 (m) 条边 DAG 图，点的标号和拓扑序一致。
现在有两个人进行博弈，有两个棋子分别在 (1, 2) 号点上，需要不断移动到它指向的点上。
如果当前两个点都无法移动，那么就视为当前操作的人失败。
问有多少边集满足先手必胜。
(displaystyle 2 le n le 15, m le frac{n imes (n+1)}{2})
题解
参考了 wxh010910 大佬的博客 。
首先利用博弈的 SG 函数易得，如果 (1) 号点和 (2) 号点的 SG 值异或不为 (0) 则先手必败。
但这样不好计数，我们考虑它的反面，求 (1,2) 号点 SG 值异或为 (0) 的方案数。
也就是 (1,2) 号点 SG 值为 (0) 的方案数。
考虑边集显然是不现实的，改成考虑点集，令 (f(S)) 为 (S) 这个集合满足 (SG(1) = SG(2)) 的方案数。
我们考虑枚举它的一个子集 (T) 假设满足点集中所有的点 (SG) 都不为 (0) ，并且它对于 (S) 的补集 (U) 都满足 (SG) 都为 (0) 。
这是连边后的情况，连边前 (T) 集合会存在 (SG) 为 (0) 的点。
我们考虑这些点的连边方案数。
- (U) 集合内部，显然不能连边。（不然不能保证 SG 为 (0) ）
- (U o T) 随意连边。
- (T o U) 要保证 (T) 中每个点都需要有一条向 (U) 连的边（要保证 (T) 集合中的 SG 不为 (0) ）
- (T) 内部的方案数，正好就是 (f(T)) 。这是为什么呢？把 (T) 中每个点都新连向一个 (SG = 0) 的点，那么它的 (SG) 都会增加 (1) 。
然后为了保证 (SG(1)=SG(2)) 枚举 (S, T, U) 的时候需要保证 (1, 2) 同时选或同时不选。
为什么这样是对的呢？
因为我们保证了 (T) 集合的方案本身满足 (SG(1) = SG(2)) 那么之后同时 (+1) 也会满足这个性质。
(U) 集合显然也是成立的（ (SG(1) = SG(2) = 0) ）。
然后枚举的时候有细节，我们考虑枚举 (U) 为 (S) 的子集，因为 (U) 必然不为 (varnothing) ，而 (T) 可以为 (varnothing) 。
总结
对于一类关于边集的状压 (dp) ，可以考虑转化成点集，然后计算连边的方案数。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBTG(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * fh;
}
void File() {
#ifdef zjp_shadow
freopen ("F.in", "r", stdin);
freopen ("F.out", "w", stdout);
#endif
}
const int N = 15, Mod = 1e9 + 7;
int n, m, G[N], Table[1 << N], dp[1 << N];
int main () {
File();
n = read(); m = read();
For (i, 1, m) { int u = read() - 1, v = read() - 1; G[u] |= (1 << v); }
int maxsta = (1 << n) - 1; dp[0] = 1;
For (i, 0, maxsta) Table[i] = 1 << __builtin_popcount(i);
For (S, 2, maxsta) if ((S & 1) == ((S >> 1) & 1))
for (int U = S; U; U = (U - 1) & S) if ((U & 1) == ((U >> 1) & 1)) {
int Ways = 1, T = S ^ U;
For (p, 0, n - 1) if ((S >> p) & 1) {
if ((U >> p) & 1) Ways = 1ll * Table[G[p] & T] * Ways % Mod;
else Ways = 1ll * (Table[G[p] & U] - 1) * Ways % Mod;
}
dp[S] = (dp[S] + 1ll * Ways * dp[T]) % Mod;
}
int ans = 1; For (i, 1, m) ans = (ans << 1) % Mod;
printf ("%d
", (ans + Mod - dp[maxsta]) % Mod);
return 0;
}