AGC016F 题解

$SG$ 函数的妙用。

1. 题意

给定一个有向图，其中边都是小编号向大编号连边。现在 Alice 和 Bob 交替移动两个石子。两个石子最开始在 1 和 2。

现在要求只保留一些边，求在剩下的图中 Alice 能胜的情况个数。答案模 $1e9 + 7$。

2. 题解

很明显，我们需要求 $sg(1) != sg(2)$ 的方案数，这个可以简单的用总数减 $sg(1) = sg(2)$ 的方案数。

怎么做呢？

我们枚举点集 $S$，让这些点的 $sg(x) = 0$，设剩下的点集为 $T$。

明显，$S$ 之间没有边，$T$ 中的点都有至少一条边连向 $S$。

然后，我们如果将 $S$ 删去，那么 $sg(x), x\in T$ 都会减 1。于是就可以从 $f(T)$ 转移到 $f(S \cup T)$。

题目给的限制就是 $1, 2$ 被分在同一个集合里了。

我们暴力枚举 $S$，枚举子集的时间复杂度为 $O(3 ^ n)$，可以通过。

总结：删掉 $sg = 0$ 的状态，所有状态 $sg$ 减一。

for (int u, v, i = 1; i <= m; ++ i)
{
	std::cin >> u >> v;
	out[-- u] |= (1 << -- v);
}
f[0] = 1;
for (int i = 1; i < (1 << n); ++ i)
	for (int j = i; j; j = (j - 1) & i){
		if ((i & 1) ^ (i >> 1 & 1)) break;
		if ((j & 1) ^ (j >> 1 & 1)) continue;
		LL now = 1;
		for (int k = 0; k < n; ++ k)
			if ((i ^ j) >> k & 1) now = now * (pw[cnt[out[k] & j]] - 1) % Mod;
			else if (j >> k & 1) now = now * (pw[cnt[out[k] & (i ^ j)]]) % Mod;
		f[i] = (f[i] + f[i ^ j] * now) % Mod;
	}