【AGC016F】Games on DAG（SG函数，状压DP，子集枚举）

93 阅读 0 评论 62 点赞

我是靠谱客的博主顺心哑铃，这篇文章主要介绍【AGC016F】Games on DAG（SG函数，状压DP，子集枚举），现在分享给大家，希望可以做个参考。

Description

有一个DAG,1号点和2号点各有一个石子.两个玩家交替将其中一个石子沿着一条有向边移动,不能移动的玩家输掉游戏.问有多少种选边的方案使得先手必胜.

Solution

将题目的条件转化成 $1$ 号点和 $2$ 号点的SG函数不相等.
我们设 $f_{S}$ 表示对于点集 $mathbf{S}$ 有多少种选边方案使得1号点和2号点 $SG$ 函数相等.( $S$ 要么同时包含 $1,2$ ,要么同时不包含 $1,2$ )
对于当前枚举的点集 $A$ ,我们枚举它的子集 $B$ 以及 $C=complement_A B$ , $B$ 表示SG函数为 $0$ 的点集, $C$ 表示SG函数非 $0$ 的点集.
我们考虑怎么连边:
1. $B$ 内部不能连边(一旦连边,SG函数就不等于 $0$ 了)
2. $C$ 内部连边方案数为 $f_{C}$ ,即在原来点集 $C$ 的基础上,每一个点的 $SG$ 函数都加 $1$
3. $Brightarrow C$ :乱连,不会对SG函数值造成影响
4. $Crightarrow B$ : $C$ 中的每一个点至少向一个 $B$ 中的点连边

然后通过子集枚举来转移即可.

Code

复制代码

/************************************************
 * Au: Hany01
 * Date: Aug 27th, 2018
 * Prob: [AGC016F] Games on DAG
 * Email: hany01dxx@gmail.com & hany01@foxmail.com
 * Inst: Yali High School
************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(), a.end()
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define count __builtin_popcount
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read() {
    static int _, __; static char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}

const int maxn = 15, maxs = 1 << 15, MOD = 1e9 + 7;

int n, m, To[maxn], f[maxs];

inline int ad(int x, int y) { if ((x += y) >= MOD) return x - MOD; return x; }
#define chk(x) (!((x) & 3) || ((x) & 3) == 3)

int main()
{
#ifdef hany01
    freopen("agc016f.in", "r", stdin);
    freopen("agc016f.out", "w", stdout);
#endif

static int uu, vv;

n = read(), m = read();
    For(i, 1, m) uu = read() - 1, vv = read() - 1, To[uu] |= (1 << vv);

f[0] = 1;
    For(A, 1, (1 << n) - 1) if (chk(A))
        for (int B = A, res, C; B; (-- B) &= A) if (chk(B)) {
            res = f[C = A ^ B];
            rep(i, n)
                if (B >> i & 1) res = (LL)res * (1 << count(To[i] & C)) % MOD;
                else if (C >> i & 1) res = (LL)res * ((1 << count(To[i] & B)) - 1) % MOD;
            f[A] = ad(f[A], res);
        }
    printf("%dn", ad((1ll << (m >> 1)) % MOD * ((1ll << (m - (m >> 1))) % MOD) % MOD, MOD - f[(1 << n) - 1]));

return 0;
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/************************************************
 * Au: Hany01
 * Date: Aug 27th, 2018
 * Prob: [AGC016F] Games on DAG
 * Email: hany01dxx@gmail.com & hany01@foxmail.com
 * Inst: Yali High School
************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(), a.end()
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define count __builtin_popcount
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read() {
    static int _, __; static char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}

const int maxn = 15, maxs = 1 << 15, MOD = 1e9 + 7;

int n, m, To[maxn], f[maxs];

inline int ad(int x, int y) { if ((x += y) >= MOD) return x - MOD; return x; }
#define chk(x) (!((x) & 3) || ((x) & 3) == 3)

int main()
{
#ifdef hany01
    freopen("agc016f.in", "r", stdin);
    freopen("agc016f.out", "w", stdout);
#endif

    static int uu, vv;

    n = read(), m = read();
    For(i, 1, m) uu = read() - 1, vv = read() - 1, To[uu] |= (1 << vv);

    f[0] = 1;
    For(A, 1, (1 << n) - 1) if (chk(A))
        for (int B = A, res, C; B; (-- B) &= A) if (chk(B)) {
            res = f[C = A ^ B];
            rep(i, n)
                if (B >> i & 1) res = (LL)res * (1 << count(To[i] & C)) % MOD;
                else if (C >> i & 1) res = (LL)res * ((1 << count(To[i] & B)) - 1) % MOD;
            f[A] = ad(f[A], res);
        }
    printf("%dn", ad((1ll << (m >> 1)) % MOD * ((1ll << (m - (m >> 1))) % MOD) % MOD, MOD - f[(1 << n) - 1]));

    return 0;
}