Submission #1417815

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = (int)1e9 + 7;

void add(int &a, ll b) {
    a = (a + b) % MOD;
}

int fastsolve(vector<vector<int> > e) {
    int n = e.size();

    vector<vector<int> > g(n);
    int all = 1;
    for (int i = 0; i < n; i++) {
        for (int to : e[i]) {
            g[to].push_back(i);
            all = 2 * all % MOD;
        }
    }
    vector<int> cov(1 << n);
    vector<int> cntEdges(1 << n);
    vector<vector<int> > cnt(1 << n, vector<int>(n));
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) continue;
            for (int to : g[i]) {
                cov[mask] |= 1 << to;
                cntEdges[mask]++;
                cnt[mask][to]++;
            }
        }
    }
    vector<int> pw(1000);
    pw[0] = 1;
    for (int i = 1; i < 1000; i++) pw[i] = pw[i - 1] * 2 % MOD;

    vector<int> dp(1 << n);
    dp[0] = 1;
    int ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == 0) continue;
        int omask = ((1 << n) - 1) ^ mask;
        for (int cmask = omask; cmask; cmask = (cmask - 1) & omask) {
            int rmask = cmask ^ omask;
            /*if ((cov[cmask] & rmask) != rmask) {
                continue;
            }*/
            int ways = dp[mask];
            for (int i = 0; i < n; i++) {
                if (rmask & (1 << i)) {
                    ways = 1LL * ways * ((1 << cnt[cmask][i]) - 1) % MOD;
                } else if (mask & (1 << i)) {
                    ways = 1LL * ways * (1 << cnt[cmask][i]) % MOD;
                }
            }
            if ((cmask & 3) == 3) add(ans, ways * 1LL * pw[cntEdges[rmask]]);
            add(dp[mask | cmask], ways);
        }
    }

    return (all - ans + MOD) % MOD;
}

int main() {
#ifdef HOME
    freopen("in", "r", stdin);
#endif

    int n, m;
    while (cin >> n >> m) {
        vector<pair<int, int> > ed(m);
        for (int i = 0; i < m; i++) {
            cin >> ed[i].first >> ed[i].second;
            ed[i].first--;
            ed[i].second--;
        }
        vector<vector<int> > e(n);
        for (int i = 0; i < m; i++) {
            e[ed[i].first].push_back(ed[i].second);
        }
        for (int i = 0; i < n; i++) {
            sort(e[i].begin(), e[i].end());
        }
        printf("%d\n", fastsolve(e));
    }

#ifdef HOME
    cerr << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

Submission Info

Judge Result