AtCoder Beginner Contest 041 D - 徒競走

問題概要

リンク

略

解法

コメント

#define MAX_N 16
int N,M;
ll dp[1 << MAX_N];
bool edge[MAX_N][MAX_N];
int main(){
    ios::sync_with_stdio(false);
    cin >> N >> M;
    REP(i, M) {
        int x, y;
        cin >> x >> y;x--;y--;
        edge[x][y] = true;
    }
    
    // dp[mask]:=mask (2進数) が1のノードだけの並び替えパターン数
    // 上記の並び替えの一番後ろにまだ使用してないノードを加えることができるかを考える
    dp[0] = 1;
    REP (i, 1 << N) {
        // j+1 bit目が0の時
        REP(j,N) if (!( (i >> j) & 1)) {
            bool isOk = true;
            // k+1 bit目が1の時 j → k というノードが存在するならアウト
            REP(k, N) if ( (i >> k) & 1) if (edge[j][k]) isOk = false;
            // j+1 bit目 を立てた場合の数にプラス
            if (isOk) dp[i + (1 << j)] += dp[i];
        }
    }
    
    cout << dp[int(1 << N)-1] << endl;
    
    return 0;
}