万能的高橋君
Games on DAG
明显的博弈论，考虑 SG 函数，结论是当初始局面的 SG 为 $0$ 时先手必败，而初始局面的 $SG = SG(1) \oplus SG(2)$
于是考虑计算 $SG(1) = SG(2)$ 的方案数，最后减掉，由于 $n \le 15$ ，可以枚举点集 $S$ ，设 $T$ 是 $S$ 的子集且 $\forall x \in T, SG(x) \ne 0$ （即 $T$ 为必胜点），设 $U = S - T$ （即 $U$ 为必败点， $SG = 0$ ），对于记当前点集 $S$ 满足 $SG(1) = SG(2)$ 的方案数为 $d[S]$
由于 SG 函数定义在 mex 上，有：
- $U$ 中的点间互相不连边
- $T$ 中的每个点至少有一条边连向 $U$
- $U$ 中的点连向 $T$ 是没有限制的
那么怎么转移呢？考虑 $S$ 的连边方案， $U$ 中的点间没边， $U, T$ 间连边的方案数设为 $tmp$ 可以算，对于 $T$ 间的边，不难发现方案数就是 $d[T]$ （这是因为原来 $d[T]$ 上的每个点都向 $U$ 连边，构成的方案一定合法；而所有点集 $S$ 的合法方案去掉 SG 为 $0$ 的点后也一定会得到一个点集 $T$ 的合法方案），故有 $d[S] \gets d[T] * tmp$
还有一个小知识点：统计一个数的二进制中有多少个 $1$
直接统计当然是 $\log n$ 的，但还有一个小技巧，就是每次让 n = n & (n - 1) 不难发现这样操作 $1$ 次后 $n$ 二进制下最低的一个 $1$ 变成了 $0$ ，于是时间为 $O(k)$ ，其中 $k$ 是二进制下 $1$ 的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
#define STC static
#define LL long long
#define get(x, o) (((x) >> (o - 1)) & 1)
using namespace std;
const int N = 20, M = 15 * 7 + 5, NN = (1 << 15) + 5, P = 1e9 + 7;
int countbit(int x)
{
int res;
for (res = 0; x; x &= (x - 1), ++res);
return res;
}
int main()
{
int n, m, nn;
STC int e[N], d[NN], pow2[M];
scanf("%d %d", &n, &m);
nn = 1 << n;
d[0] = pow2[0] = 1;
for (int i = 1; i <= m; ++i)
pow2[i] = (pow2[i - 1] << 1) % P;
for (int i = 1, u, v; i <= m; ++i)
scanf("%d %d", &u, &v), e[u] |= (1 << (v - 1));
for (int s = 1, tmp; s < nn; ++s)
if (get(s, 1) == get(s, 2))
for (int u = s; u; u = s & (u - 1))
if (get(u, 1) == get(u, 2))
{
tmp = 1;
for (int i = 1; i <= n; ++i)
if (get(s, i))
{
if (get(u, i))
tmp = (LL)tmp * pow2[countbit(e[i] & (s ^ u))] % P;
else
tmp = (LL)tmp * (pow2[countbit(e[i] & u)] - 1) % P;
}
d[s] = (d[s] + (LL)d[s ^ u] * tmp % P) % P;
}
printf("%d\n", (pow2[m] - d[nn - 1] + P) % P);
return 0;
}
|