All integers can be represented as bitmasks, strings of 0s or 1s. A bitmask of length N has 2^N states. It turns out that these bitmasks can be very useful in helping us solve a bunch of problems in time complexity of order O(2^N). In most cases, bitmasking helps us optimize from O(N!) time complexity down to O(2^N). A general rule is that if N <= 20 is a problem, then you will probably end up using bitmasking.
The state for this problem is DP[i][mask] = # of ways to perform a path ending at node i while visiting all nodes that are turned on in mask.
For example DP[3][1101] is the number of ways to end at node 3 while visiting nodes 0, 2 and 3. (0 starts from the right and 3 is the leftmost). Note that 1101 is in base 2 and is equivalent to 11 in base 10.
The transition is such: DP[i][mask] -> DP[j][mask | (1<<j)] where the edge i->j exists and node j is not turned on in our current mask. Then we will add all of our DP to the next DP state and transition.
| const int MOD = 1e9 + 7; vector<int> adj[21]; int dp[20][1 << 20]; int N, M; int solve(int cur, int mask){ if(dp[cur][mask] != -1)return dp[cur][mask]; //memoization if(mask == (1<<N) – 1){ return dp[cur][mask] = (cur == N-1); //ending state, check if we are at node N and visited all nodes } dp[cur][mask] = 0; for(int nxt : adj[cur]){ if(!(mask >> nxt & 1)){ //if we haven’t visited said node yet dp[cur][mask] += solve(nxt, mask | (1 << nxt)); //transition to next, mark our next node as visitied dp[cur][mask] %= MOD; } } return dp[cur][mask]; } int main(){ cin >> N >> M; memset(dp, -1, sizeof(dp)); for(int i = 0; i < M; i++){ int l, r; cin >> l >> r; l–,r–; adj[l].push_back(r); } cout << solve(0, 1) << endl; } |