Submission #1498876

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    //ifstream cin("f.in");

    int n, m; cin >> n >> m; 
    
    vector<vector<int>> mat(n, vector<int> (n, 0));
    vector<int> b(n, 0);

    for(int i = 0; i < m; ++i) {
        int x, y; cin >> x >> y;
        x -= 1, y -= 1;
        mat[x][y] = 1;
        b[x] |= (1 << y);
    }
    
    auto add = [&] (int &a, int b) {
        a += b;
        while(a >= MOD) {
            a -= MOD;
        }
        while(a < 0) {
            a += MOD;
        }
    };

    vector<int> dp((1 << n), 0);
    vector<int> set_bits((1 << 15), 0);
    
    for(int i = 1; i < (1 << 15); ++i) {
        set_bits[i] = set_bits[i >> 1] + (i & 1);
    }

    dp[0] = 1;

    for(int mask = 0; mask < (1 << n); ++mask) {
        for(int sub = mask; sub > 0; sub = ((sub - 1) & mask)) {
            if((sub & 1) and (sub & 2))
                continue;
            if(dp[mask - sub] == 0)
                continue;

            int ways = 1;
            for(int i = 0; i < n; ++i) {
                if((1 << i) & mask)
                    continue;
                int who = set_bits[(b[i] & sub)];
                ways = 1LL * ways * ((1 << who) - 1) % MOD;
                if(ways == 0) {
                    break;
                }
            }
            
            if(ways == 0) {
                continue;
            }

            for(int i = 0; i < n; ++i) {
                if((1 << i) & sub) {
                    int many = set_bits[b[i] & ((1 << n) - mask)];
                    ways = 1LL * ways * (1 << many) % MOD;
                }
            }

            int prv = dp[mask - sub];
            add(dp[mask], 1LL * prv * ways % MOD);
        }
    }

    int ans = dp[(1 << n) - 1];

    cout << ans << "\n";
}

Submission Info

Judge Result