[AGC016F] Games on DAG题解

例题Ⅰ：

题解：时间复杂度 O(n*3^n)

int n, m, a[N][N]; // 邻接矩阵
int twoP[N * N], dp[1 << N], cnt[1 << N][N];
// dp[I]记录集合I在必败的前提下所有的边组合方式, cnt[i][j]记录j到集合i的边数
void solve()
{
    cin >> n >> m;
    twoP[0] = 1;
    for (int i = 1; i <= m; ++i)
        twoP[i] = 2 * twoP[i - 1] % mod;
    for (int i = 1, x, y; i <= m; ++i)
    {
        cin >> x >> y;
        a[x][y] = 1;
    }
    for (int U = 1; U < 1 << n; ++U)
    {
        int j = __builtin_ffs(U) - 1; // 最后一位1的位置
        for (int u = 0; u <= n; ++u)  // 预处理cnt
            cnt[U][u] = cnt[U ^ 1 << j][u] + a[u + 1][j + 1];
    }
    for (int U = 0; U < 1 << n; ++U) // 枚举全集子集U
    {
        if((u & 3) != 3 && (u & 3) != 0) continue;
        dp[U] = 1; // 初始化集合U必败态的总数
        for (int T = U & (U - 1); T; --T &= U) // 枚举U的子集T
        {
            if ((T & 1) != (T >> 1 & 1)) // 1,2都在或都不在T
                continue;
            int S = U ^ T, coef = 1; // S是U - T
            for (int i = 0; i < n; ++i)
            {
                if (T >> i & 1)
                    coef = (ll)coef * twoP[cnt[S][i]] % mod; // T到S随便选边
                if (S >> i & 1)
                    coef = (ll)coef * (twoP[cnt[T][i]] - 1) % mod; // S到T至少选一条边
            }
            //dp[T]内部没有边,只有空集一种情况
            dp[U] = (dp[U] + (ll)coef * dp[S] % mod) % mod;
        }
    }
    cout << (twoP[m] - dp[(1 << n) - 1] + mod) % mod << endl;
}