# CFR 11 D. A Simple Task ( DP, Bitmask, Hamiltonian Walk )

Problem - 11D - Codeforces

N ≤ 19
TL: 2000 ms

dp[ s ][ i ] : 以 lowbit( s ) 為起點，拜訪 s 中每個節點恰好一次，最後在節點 i 的方法數

O( N^2 * 2^N ) / O( N * 2^N )

```#include <bits/stdc++.h>
using namespace std;

typedef vector< int > vi;

const int MAXN = 19;

int N, M;
int adj[ MAXN ][ MAXN ];
long long dp[ 1 << MAXN ][ MAXN ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < M; ++i ){
int u, v; cin >> u >> v; --u, --v;
adj[ u ][ v ] = adj[ v ][ u ] = 1;
}
for( int i = 0; i < N; ++i ){
dp[ 1 << i ][ i ] = 1;
}
for( int s = 0; s < 1 << N; ++s ){
if( __builtin_popcount( s ) < 2 ) continue;
int lobit = __builtin_ctz( s );
for( int i = 0; i < N; ++i ){
if( i == lobit ) continue;
if( ~s >> i & 1 ) continue;
for( int j = 0; j < N; ++j ){
if( ~s >> j & 1 ) continue;
if( not adj[ i ][ j ] ) continue;
dp[ s ][ i ] += dp[ s ^ 1 << i ][ j ];
}
}
}
long long ans = 0;
for( int s = 0; s < 1 << N; ++s ){
if( __builtin_popcount( s ) < 3 ) continue;
int lobit = __builtin_ctz( s );
for( int i = 0; i < N; ++i ){
if( i == lobit ) continue;
if( not adj[ i ][ lobit ] ) continue;
ans += dp[ s ][ i ];
}
}
cout << ans / 2 << endl;
return 0;
}
```