AtCoder Grand Contest 016F - Games on DAG

#博弈 #动态规划 #状态压缩动态规划
Published on 2017-07-01

题目地址

描述

给定一个 n(2≤n≤15)n(2\le n\le 15) 个点的 DAG，m(1≤m≤n(n−1)/2)m(1\le m\le n(n - 1) / 2) 条有向边 (xi,yi)(xi<yi)(x_i, y_i)(x_i < y_i)。问所有 2m2^m 种边的选取方案中，有多少种方案使得形成的图中，点 11 和点 22 的 SG 值不同？

答案对 109+7{10}^9 + 7 取模。

分析

考虑有多少种方案使得 SG(1)=SG(2)\mathrm{SG}(1) = \mathrm{SG}(2)。考虑 SG(v)\mathrm{SG}(v) 的计算方式

SG(v)=mexu∈Gv{SG(u)} \mathrm{SG}(v) = \mathrm{mex}_{u\in G_v}\{\mathrm{SG}(u)\}

我们可以将点分为两类，一类是 SG 值为 00 的点，一类是 SG 值不为 00 的点，并以此来 DP。设 dp(s)dp(s) 为只考虑 ss 中的点，有多少边的选取方案使得点 00 和点 11 的 SG 值相同，这里需要保证要么点 00 和点 11 都不在 ss 中，要么都在 ss 中，否则 ss 不是一个合法状态。

转移考虑枚举 ss 的子集 u(u≠∅)u(u\neq\emptyset)，表示 uu 中的点 SG 值全为 00，uu 的补集为 tt，表示 tt 中的点 SG 值全不为 00，那么 uu 和 tt 的连边情况如下：

  1. uu 内部没有任何连边。
  2. uu 向 tt 可以随意连边。
  3. tt 中的每个点至少向 uu 中的一个点连边。
  4. tt 内部的连边方案数就是 dp(t)dp(t)。

第四条非常巧妙，由于 tt 中的 SG 值全不为 00，我们给 tt 中的每个点都连向了一个 SG 值为 00 的点，对应到 dp(t)dp(t) 的每个方案，相当于 tt 中所有点的 SG 值都加一，容易看出这样是不重不漏的。

预处理一下 cnt(i,s)\mathrm{cnt}(i, s) 为点 ii 向 ss 中的点连边，最多能连多少条。预处理复杂度 O(2nn)O(2^nn)，由于 DP 需要枚举子集，复杂度 O(3nn)O(3^nn)，总复杂度 O(3nn)O(3^nn)。

代码

//  Created by Sengxian on 2017/6/30.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  AGC016F 博弈 + 状压 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    int n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 15, MOD = 1000000007;
int n, m, G[MAX_N], popCount[1 << MAX_N], cnt[MAX_N][1 << MAX_N];
int dp[1 << MAX_N];

inline bool check(int s) {
    return (s & 3) == 0 || (s & 3) == 3;
}

void prepare() {
    popCount[0] = 0;
    for (int s = 1; s < (1 << n); ++s)
        popCount[s] = popCount[s >> 1] + (s & 1);
    for (int s = 0; s < (1 << n); ++s)
        for (int i = 0, t = s; i < n; ++i, t &= ~(1 << i))
            cnt[i][s] = popCount[t & G[i]];
}

void solve() {
    dp[0] = 1;
    for (int s = 1; s < (1 << n); ++s) if (check(s)) {
        int t = s;
        for (int u = s; u; u = (u - 1) & s) {
            int t = s ^ u, res = dp[t];
            if (!check(t)) continue;
            // u all zero
            // t all non-zero
            // u -> t
            for (int i = 0; i < n; ++i) if (u >> i & 1)
                res = (ll)res * (1 << cnt[i][t]) % MOD;
            // t -> u
            for (int i = 0; i < n; ++i) if (t >> i & 1)
                res = (ll)res * ((1 << cnt[i][u]) - 1) % MOD;
            (dp[s] += res) %= MOD;    
        }
    }

    int res = 1;
    for (int i = 0; i < m; ++i) (res *= 2) %= MOD;
    printf("%d\n", (res - dp[(1 << n) - 1] + MOD) % MOD);
}

int main() {
    n = readInt(), m = readInt();
    for (int i = 0; i < m; ++i) {
        int u = readInt() - 1, v = readInt() - 1;
        G[u] |= 1 << v;
    }

    prepare();
    solve();

    return 0;
}