Broken profile DP: как посчитать число замощений доски n×m доминошками 1×2?

Broken profile DP — обходим клетки по столбцам (или строкам) одну за другой, а состояние = профиль — битовая маска из n бит, описывающая «границу» между уже заполненной и ещё пустой частью. Бит j профиля = «клетка в строке j на границе уже занята выступом доминошки слева».

Идём по клеткам (col, row) в порядке столбец-за-столбцом. Для текущей клетки три варианта: она уже занята (из предыдущего хода), поставить горизонтальную доминошку (займёт текущую и клетку справа), поставить вертикальную (текущую и снизу).

int n, m; // n <= 16 строк, m столбцов
// dp[mask] = число замощений до текущей клетки с профилем mask
vector<long long> dp(1 << n, 0), ndp;
dp[0] = 1;
for (int col = 0; col < m; ++col)
  for (int row = 0; row < n; ++row) {
    ndp.assign(1 << n, 0);
    for (int mask = 0; mask < (1 << n); ++mask) {
      if (dp[mask] == 0) continue;
      if (mask & (1 << row)) {                    // клетка уже занята
        ndp[mask ^ (1 << row)] += dp[mask];        // снимаем бит, идём дальше
      } else {
        // вертикальная доминошка: занимает (row) и (row+1)
        if (row + 1 < n && !(mask & (1 << (row + 1))))
          ndp[mask | (1 << (row + 1))] += dp[mask];
        // горизонтальная: занимает текущую и клетку в след. столбце
        if (col + 1 < m)
          ndp[mask | (1 << row)] += dp[mask];
      }
    }
    dp = ndp;
  }
// ответ dp[0]

Сложность: клеток $n\cdot m$, на каждой перебор $2^n$ профилей → время $O(n \cdot m \cdot 2^n)$, память $O(2^n)$. Для $n=16$: $2^{16}=65536$, умножаем на $n\cdot m$ — заходит при разумных $m$.