# Bitmask DP

Authors: Michael Cao, Siyong Huang

Contributors: Andrew Wang, Neo Wang

DP problems that require iterating over subsets.

### Pro Tip

You can often use this to solve subtasks.

## Bitmask DP

Focus Problem – try your best to solve this problem before continuing!

### Tutorial

Resources | ||||
---|---|---|---|---|

CPH | Elevator Rides, SOS, Hamiltonian | |||

nwatx | ||||

PAPS | example - similar to Hamiltonian | |||

CF | Hamiltonian walks | |||

DPCC | Diagram | |||

HE |

### 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$.

C++

#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

### Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

AC | Easy | ## Show TagsBitmasks, DP | |||

CF | Easy | ## Show TagsBitmasks, MinCostFlow | |||

Old Gold | Easy | ## Show TagsBitmasks, DP | |||

Old Gold | Easy | ## Show TagsBitmasks, DP | |||

Gold | Normal | ## Show TagsBitmasks, DP | |||

CSES | Normal | ## Show TagsBitmasks, DP | |||

IZhO | Normal | ## Show TagsBitmasks, DP | |||

Kattis | Normal | ## Show TagsBinary Search, Bitmasks, DP, Geometry | |||

YS | Hard | ## Show TagsBitmasks, DP, Meet in Middle | |||

IZhO | Hard | ## Show TagsBitmasks, DP | |||

COCI | Hard | ## Show TagsBitmasks, DP, Game Theory, Tree | |||

Gold | Hard | ## Show TagsBitmasks, DP | |||

CEOI | Very Hard | ## Show TagsBitmasks, DP | |||

IOI | Very Hard | ## Show TagsBitmasks, DFS, DP, Tree |

## Application - Bitmask over Primes

### Rough Idea

In some number theory problems, it helps to represent each number were represented by 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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Hard | ## Show TagsCombinatorics, DP | |||

CF | Very Hard | ## Show TagsBitmasks, DP, NT | |||

CF | Insane | ## Show TagsBinary Search, Bitmasks, NT | |||

CF | Insane | ## Show TagsBitmasks, Combinatorics, DP |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!