Фрактальне розширення (Розбір)

Розв'язання

Кожен рядок, який може виникнути під час процесу, є префіксом рядка $t$.

Нехай $dp[x]$ — мінімальна вартість, необхідна для отримання префікса $t$ довжини $x$.

Спочатку

З кожного стану існує два можливих переходи.

Додавання одного символу

Нехай поточний префікс має довжину $x$.

Після додавання наступного символу його довжина стане рівною x+1, а вартість операції дорівнює x+1.

Отже,

Застосування перетворення

Нехай поточний рядок має вигляд

Позначимо

Кожен символ A перетворюється на два символи, а кожен символ B — на один.

Тому

Після застосування операції рядок стає

а його нова довжина дорівнює

Операція є допустимою рівно тоді, коли

Тепер побудуємо рядок

Оскільки перетворення застосовується до кожного символу незалежно,

є рівно префіксом $U$ довжини L_x.

Отже, потрібно лише перевірити

Це запит на довжину найбільшого спільного префікса між $U$ та суфіксом $t$, який починається з позиції x+1.

Побудуємо рядок

де # — символ, відмінний від A та B, і порахуємо його Z-функцію.

Значення Z-функції у позиції, що відповідає x+1 у рядку $t$, дорівнює довжині спільного префікса між $U$ та

Таким чином, операцію можна виконати рівно тоді, коли

та відповідне значення Z-функції не менше за L_x.

У такому випадку виконуємо перехід

Відповіддю буде $dp[n]$.

Доведення коректності

Кожен досяжний рядок є префіксом $t$, тому достатньо зберігати лише його довжину.

З префікса довжини $x$ можливі рівно дві операції: додати один символ або застосувати перетворення.

Перший перехід динаміки точно відповідає операції додавання символу.

Для другого переходу Z-функція точно перевіряє, чи знаходиться f(t_1t_2\dots t_x) безпосередньо після поточного префікса.

Отже, ми враховуємо всі допустимі переходи та не додаємо жодного недопустимого.

Тому $dp[x]$ містить мінімальну вартість отримання префікса довжини $x$, а $dp[n]$ є шуканою відповіддю.

Складність

Довжина рядка $U$ не перевищує $2n$.

Побудова $U$, підрахунок кількості символів A у префіксах та обчислення Z-функції займають $O(n)$ часу.

Кожен стан динаміки має не більше двох переходів.

Отже, загальна складність становить

за часом та

за пам'яттю.