【题解】[AGC016F] Games on DAG

题目链接：[AGC016F] Games on DAG

题意：

给定 $n$ 个点 $m$ 条边的 $\text{DAG}$，现在 $1,2$ 号点上分别有一个棋子。$\text{Alice}$ 和 $\text{Bob}$ 轮流选择一个棋子，将其向一条出边移动。不能移动者败，问 $2^m$ 张生成子图中，有多少先手必胜。
$2\le n\le 15$，$1\le m\le {(n-1)\times n\over 2}$，$\text{5s}$。

根据博弈论结论，先手必胜当且仅当初始局面 $\text{SG}\ne 0$。而两颗棋子独立，所以局面 $\text{SG}$ 为 $\text{SG(1)}\text{ xor }\text{SG(2)}$。转变为计数先手必败的情况，则 $\text{SG(1)}=\text{SG(2)}$。

考虑到 $n$ 很小，所以节点的 $\text{SG}$ 值不会很大。因此考虑枚举 $\text{SG}$ 值为一个固定值 $k$ 的集合，计算使当前划分方案成立的 $\text{DAG}$ 的个数。

从小到大确定 $\text{SG}$ 的集合不太好做，因为需要做的是形如：“在每一个 $\text{SG}<k$ 的集合中选择一个元素与当前点连边”，这样就与每一个集合的具体大小相关了。

但从大到小不一样，$\text{SG}>k$ 的所有元素对当前集合都是一样的——都可以随便连过去。

因此设 $S$ 是 $\text{SG}>k$ 的集合，$T$ 是 $\text{SG}=k$ 的集合。则 $1,2$ 同时在 $T$ 或同时不在 $T$。

• 对于 $S\rightarrow T$ 的边，每一个 $S$ 中的元素都至少要向 $T$ 中连一条边。
• 对于 $T\rightarrow S$ 的边，随便连都可以。
• 对于 $T$ 内部的边，一条都不能连。

因此就得到了一个 $\mathcal{O}(n\times 3^n)$ 的算法。

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 18;
const int MAXS = (1 << 17) + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m;
int cnt[MAXN][MAXS], p2[MAXN * MAXN];
int link[MAXN][MAXN];
int dp[MAXS];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

bool chk(int T) {
    if((T & 1) + ((T >> 1) & 1) == 1) return false;
    return true;
}

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(n), read(m); p2[0] = 1;
    for(int i = 1; i <= m; ++i) p2[i] = p2[i - 1] * 2 % mod;
    for(int i = 1, x, y; i <= m; ++i) {
        read(x), read(y);
        link[x][y]++;
    }
    for(int S = 0; S < (1 << n); ++S)
        for(int i = 1; i <= n; ++i) {
            cnt[i][S] = cnt[i][S ^ lowbit(S)];
            if(S) cnt[i][S] += link[i][(int)log2(lowbit(S)) + 1];
        }
    dp[0] = 1;
    for(int S = 1; S < (1 << n); ++S) {
        for(int T = S, K, coe; T; T = (T - 1) & S) {
            K = S ^ T, coe = 1; if(!chk(T)) continue;
            for(int i = 1; i <= n; ++i) {
                if((T >> (i - 1)) & 1) coe = coe * p2[cnt[i][K]] % mod;
                if((K >> (i - 1)) & 1) coe = coe * (p2[cnt[i][T]] - 1) % mod;
            }
            (dp[S] += dp[K] * coe) %= mod;
        }
    }
    printf("%lld\n", (p2[m] - dp[(1 << n) - 1] + mod) % mod);
    return 0;
}