Zadanie z kombinatoryki (chyba) na ile różnych sposobów można wejść na wierzołek czworościanu foremnego[CodeForces]

Question

Mam takie zdanie: https://codeforces.com/problemset/problem/166/E
I rozwiązanie do niego: https://codeforces.com/blog/entry/4173
Z rozwiązania rozumiem, że można być w 4 miejscach i miejsca ABC nie różnią się niczym. Nie rozumiem co oznaczają te nazwy zmiennych i dlaczego to działa

int zD = 1;
int zABC = 0;
for (int i = 1; i <= n; i++) {
    int nzD = zABC * 3LL % MOD;
    int nzABC = (zABC * 2LL + zD) % MOD;
    zD = nzD;
    zABC = nzABC;
}
cout << zD;

Czy ktoś mógłby pomóc mi zrozumieć dlaczego to działa, co się w tym kodzie dzieje i napisać nazwy zmiennych na czytelniejsze ?

Answer 1

Żeby rozjaśnić ten kod to na początku pokażę jak to można rozwiązać bardziej czytelnie. Powiedzmy, że dp[i][v] to ilosć sposobów na dojście do wierzchołka v wykonując i ruchów, wtedy otrzymujesz następujące przejścia między stanami:

dp[i][D] = dp[i-1][A] + dp[i-1][B] + dp[i-1][C]

dp[i][A] = dp[i-1][B] + dp[i-1][C] + dp[i-1][D]

dp[i][B] = dp[i-1][A] + dp[i-1][C] + dp[i-1][D]

dp[i][C] = dp[i-1][A] + dp[i-1][B] + dp[i-1][D]

Kod który podałeś korzysta z takiej zależności, że dp[i][A] = dp[i][B] = dp[i][C], więc możemy te stany traktować jako jeden. Wtedy zD to dp[i][D], zABC to dp[i][A].