Submission #1308040

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

bool is_valid(int idx, long long prev, const vector<vector<bool>> & xy){
    int pos = 0;
    while (prev){
        if (prev & 1){
            if (xy[idx][pos]) return false;
        }
        prev >>= 1;
        ++pos;
    }
    return true;
}

void update_dp(long long pat, int N, vector<long long> & dp,const vector<vector<bool>> & xy){
    for (int idx = 0; idx != N; ++idx){
        if (pat & (1LL << idx)){
            long long prev = pat - (1LL << idx);
            if (dp[prev] and is_valid(idx, prev, xy)) dp[pat] += dp[prev];
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    long long L = 1LL << N;
    vector<vector<bool>> xy(N, vector<bool>(N, false));
    for (int m = 0; m != M; ++m){
        int x, y;
        cin >> x >> y;
        xy[x - 1][y - 1] = true;
    }
    vector<long long> dp(L, 0LL);
    dp[0] = 1LL;
    for (long long pat = 1LL; pat != L; ++pat){
        update_dp(pat, N, dp, xy);
    }
    cout << dp[L - 1] << endl;
    return 0;
}

Submission Info

Judge Result