Bitmask Dynamic Programming (Bitmask DP) is a technique used to solve problems where the state of a system can be represented by a small set of binary flags. By using an integer's bits to store boolean information—where each bit corresponds to a specific element's status—we can compactly represent and manipulate complex configurations.

Core Concepts

The fundamental idea is to map a seqeunce of boolean states into an integer. For instance, if you have a row of $n$ cells, the state of whether each cell is "occupied" (1) or "empty" (0) can be represented by an integer in the range $[0, 2^n - 1]$. This approach is highly effective when $n$ is small (typically $n \le 20$), as the exponential growth of state space ($2^n$) quick becomes unmanageable for larger constraints.

Illustrative Problem: Non-Attacking Rooks

Given an $n \times n$ chessboard with certain restricted cells, determine the number of ways to place $n$ non-attacking rooks. Since each row and column can contain only one rook, we can represent the configuration by tracking which columns are already occupied using a bitmask.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

ll solve_rooks() {
   int n, m;
   cin >> n >> m;
   vector<int> restricted(n + 1, 0);
   for (int i = 0; i < m; ++i) {
       int r, c;
       cin >> r >> c;
       restricted[r] |= (1 << (c - 1));
   }

   vector<ll> dp(1 << n, 0);
   dp[0] = 1;

   for (int mask = 0; mask < (1 << n) - 1; ++mask) {
       int row = __builtin_popcount(mask) + 1;
       for (int col = 0; col < n; ++col) {
           if (!(mask & (1 << col)) && !(restricted[row] & (1 << col))) {
               dp[mask | (1 << col)] += dp[mask];
           }
       }
   }
   return dp[(1 << n) - 1];
}

Common Techniques

• State Pre-processing: For problems like "Kings" (where neighbors cannot be adjacent), pre-calculate all valid configurations for a single row to prune the state space.
• Transition Constraints: When transitioning between rows (e.g., in grid-based problems), use bitwise operators such as (maskA & maskB) == 0 to ensure vertical adjacency rules are respected.
• Ring-Buffer Mapping: For circular dependencies, you can iterate over the possible states of the first position and fix it, effectively "unrolling" the ring into a linear structure.

Advanced Pattern: The "Angry Birds" Approach

In problems involving covering elements with sets (like parabolas hitting pigs), identify all possible "covering patterns" beforehand. Represent each pattern as an integer mask. The transition then becomes: dp[mask | pattern] = min(dp[mask | pattern], dp[mask] + 1). This transforms the problem into a variation of the Set Cover problem, solvable in $O(2^n \cdot n^2)$ or similar complexities.