Bitmask DP

Bitmask DP

Tutorial

Solution

Let $dp[S][i]$ be the number of routes that visit all the cities in the subset $S$ and end at city $i$. The transitions will then be:

where $S \setminus \{i\}$ is the subset $S$ without city $i$.

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

using ll = long long;

const int MAX_N = 20;
const ll MOD = (ll)1e9 + 7;

ll dp[1 << MAX_N][MAX_N];
// come_from[i] contains the cities that can fly to i

Copy
import sys

MOD = 10**9 + 7

input = sys.stdin.readline

n, m = map(int, input().strip().split())
dp = [[0 for _ in range(n)] for _ in range(1 << n)]
dp[1][0] = 1

Problems

Application - Bitmask over Primes

Rough Idea

In some number theory problems, it helps to represent each number with a bitmask of its prime divisors. For example, the set $\{6, 10, 15 \}$ can be represented by $\{0b011, 0b101, 0b110 \}$ (in binary)*, where the bits correspond to divisibility by $[2, 3, 5]$.

Then, here are some equivalent operations between masks and these integers:

• Bitwise AND is GCD
• Bitwise OR is LCM
• Iterating over bits is iterating over prime divisors
• Iterating over submasks is iterating over divisors

Choosing a set with GCD $1$ is equivalent to choosing a set of bitmasks that AND to $0$. For example, we can see that $\{6, 10 \}$ doesn't have GCD $1$ because $0b011 \& 0b101 = 0b001 \neq 0$. On the other hand, $\{6, 10, 15 \}$ has GCD $1$ because $0b011 \& 0b101 \& 0b110 = 0b000 = 0$.

Problems