Four Steps#13107

Four Steps (Editorial)

For a string of digits , let c_0, c_{01}, c_{012} and c_{0123} be the numbers of its subsequences equal to 0, 01, 012 and 0123; the number of climbs is c_{0123}. Appending one digit changes exactly one of the counters, and only by adding another one:

\texttt{0}\colon\ c_0 \mathrel{+}= 1, \qquad \texttt{1}\colon\ c_{01} \mathrel{+}= c_0, \qquad \texttt{2}\colon\ c_{012} \mathrel{+}= c_{01}, \qquad \texttt{3}\colon\ c_{0123} \mathrel{+}= c_{012}.

Indeed, a new occurrence of 01 must end at the new 1, and its 0 is any of the c_0 earlier zeros; the other digits are similar.

Key observation. We only need c_{0123} \bmod 4, and since the updates use nothing but additions, all four counters can be kept modulo from the start: reducing modulo commutes with addition, so the reduced counters after every prefix are exactly the true counters reduced modulo . The true counts are huge (the number of climbs can exceed 2^{64}), but they are never needed.

So the whole string is processed by an automaton with 4^4 = 256 states (c_0, c_{01}, c_{012}, c_{0123}) \bmod 4, starting in (0,0,0,0). Let be the number of ways to fill the ? of the current prefix so that it ends in state , modulo . A fixed digit moves each to the state given by its update; a ? adds to each of the four successors of . The answer is the sum of over the states with c_{0123} \equiv 0 \pmod 4. Only the current layer of has to be stored; precomputing the successor of every state for every digit keeps the inner loop simple.

All states are needed: for instance, keeping c_0 only modulo is wrong, because c_0 is later multiplied by the number of 123 after it, which may be odd.

The complexity is O(256 \cdot 4 \cdot |s|) per test case, with memory.