Bitmask DP с состоянием 3^n: как считать ДП, где каждый элемент в одном из трёх состояний?

Когда у элемента три состояния, естественное кодирование — число в троичной системе: конфигурация = число от $0$ до $3^n - 1$, где i-я троичная цифра ∈ {0,1,2} — состояние i-го объекта.

Извлечение/установка троичной цифры:

int n; // <= 12, т.к. 3^12 ~ 531441
vector<int> pow3(n + 1);
pow3[0] = 1;
for (int i = 1; i <= n; ++i) pow3[i] = pow3[i - 1] * 3;

// получить состояние объекта i из конфигурации mask
auto get = [&](int mask, int i){ return (mask / pow3[i]) % 3; };
// установить объекту i состояние v (0..2)
auto setv = [&](int mask, int i, int v){
  int cur = get(mask, i);
  return mask + (v - cur) * pow3[i];
};

vector<long long> dp(pow3[n], 0);
dp[0] = 1; // все объекты в состоянии 0
for (int mask = 0; mask < pow3[n]; ++mask) {
  if (dp[mask] == 0) continue;
  // ... переходы, меняющие состояние объектов через setv ...
}

Число состояний $3^n$. Если переход перебирает объект ($O(n)$) — итого $O(3^n \cdot n)$. Для $n=12$: $3^{12}\approx 5.3\cdot10^5$, умножить на 12 → $\sim 6\cdot10^6$ — быстро. Но рост резкий: $n=16$ даёт $3^{16}\approx 4.3\cdot10^7$, а $n=20$ — уже $3.5\cdot10^9$ (TLE). Поэтому троичные маски — для маленьких $n$.