Чотири сходинки#13107

Чотири сходинки (Розбір)

Для рядка цифр позначимо через c_0, c_{01}, c_{012} і c_{0123} кількості його підпослідовностей, що дорівнюють 0, 01, 012 і 0123; кількість сходжень — це c_{0123}. Дописування однієї цифри змінює рівно один лічильник, і лише додаванням іншого:

\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}.

Справді, нове входження 01 мусить закінчуватися новою 1, а його 0 — будь-який із c_0 попередніх нулів; для інших цифр аналогічно.

Ключове спостереження. Нам потрібне лише c_{0123} \bmod 4, а оскільки оновлення використовують тільки додавання, усі чотири лічильники можна від самого початку зберігати за модулем : взяття за модулем комутує з додаванням, тож зведені лічильники після кожного префікса — це саме справжні лічильники за модулем . Справжні кількості величезні (сходжень може бути більше за 2^{64}), але вони ніколи не потрібні.

Отже, увесь рядок обробляє автомат із 4^4 = 256 станами (c_0, c_{01}, c_{012}, c_{0123}) \bmod 4, що стартує в (0,0,0,0). Нехай — кількість способів заповнити ? поточного префікса так, щоб він закінчився у стані , за модулем . Фіксована цифра переносить кожне у стан, заданий її оновленням; ? додає до кожного з чотирьох наступників . Відповідь — сума за станами з c_{0123} \equiv 0 \pmod 4. Зберігати треба лише поточний шар ; якщо заздалегідь обчислити наступника кожного стану для кожної цифри, внутрішній цикл стає зовсім простим.

Усі станів потрібні: наприклад, зберігати c_0 лише за модулем неправильно, бо згодом c_0 множиться на кількість 123 після нього, а вона може бути непарною.

Складність — O(256 \cdot 4 \cdot |s|) на тестовий випадок, пам'ять — .