ABC 041 D - 徒競走 ( bit DP )

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
またも面白い問題。
トポロジカルソートに注意しすぎた。でも N の小ささを見れば大抵 bit DP だとわかる。
dp( S ) : number of valid topological sorted array for S and the restrictions given

int N, M;
int X[ MAXM ], Y[ MAXM ];

int G[ MAXN ][ MAXN ];

void solve(){
    cin >> N >> M;
    for( int i = 0; i < M; ++i )
        cin >> X[ i ] >> Y[ i ],
        --X[ i ], --Y[ i ],
        G[ X[ i ] ][ Y[ i ] ] = 1; // X[ i ] -> Y[ i ]

    vi dp( 1 << N );
    dp[ 0 ] = 1;
    for( int S = 0; S < 1 << N; ++S ){
        for( int i = 0; i < N; ++i ) if( not( S >> i & 1 ) ){
            bool ng = false;
            for( int j = 0; j < N; ++j ) if( S >> j & 1 )
                if( G[ i ][ j ] ) // unfortunately i cannot be last element
                    ng = true;   // because j is after i
            if( not ng )
                dp[ S | 1 << i ] += dp[ S ];
        }
    }

    cout << dp[ ( 1 << N ) - 1 ] << "\n";
}