\begin{tutorial}{Hanoi Towers Reloaded}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Артем Васильев \\
         Разработка: & Артем Васильев \\
     \end{tabular}
}

Решим частный случай: переложить все $n$ дисков со стержня 1 на стержень 3, что в терминах задачи соответствует состояниям \t{1 1 ... 1} и \t{3 3 ... 3}. Обозначим нужное число ходов за $f(n)$.
Аналогично классической задаче про Ханойские башни, приведем рекурсивный алгоритм. Для нуля дисков нужно ноль ходов: $f(0) = 0$. 

Для $n$ дисков рассмотрим, как мы перемещаем самый большой: сначала $1 \to 2$, затем $2 \to 3$. Для хода $1 \to 2$ необходимо, чтобы все остальные диски были на стержне $3$, а для хода $2 \to 3$ необходимо, чтобы все остальные диски были на стержне $1$. Получаем следующую последовательность действий для $n$ дисков:

\begin{itemize}
\item Переложить диски $1 \ldots n-1$ со стержня 1 на стержень 3, рекурсивно за $f(n-1)$ шагов;
\item Переложить диск $n$ с 1 на 2;
\item Переложить диски $1 \ldots n-1$ с 3 на 1, рекурсивно за $f(n-1)$ шагов;
\item Переложить диск $n$ с 2 на 3;
\item Переложить диски $1 \ldots n-1$ с 1 на 3, рекурсивно за $f(n-1)$ шагов.
\end{itemize}

Всего шагов получается $f(n) = f(n-1) + 1 + f(n-1) + 1 + f(n-1) = 3f(n-1) + 2$. Решением этого рекуррентного соотношения является $f(n) = 3^n - 1$. 

Заметим, что в этой последовательности нет повторяющихся состояний. Всего различных состояний в этой задаче $3^n$: каждый из дисков может быть на одном из трех стержней, порядок дисков на стержне фиксирован. Также, из каждого состояния (кроме \t{1 1 ... 1} и \t{3 3 ... 3}) существует ровно два возможных хода: если самый маленький диск находится на стержне $2$, его можно переложить на $1$ или $3$, а если он лежит с краю, то между оставшимися двумя стержнями можно сделать один ход.

Из всех утверждений, описанных выше, можно сделать вывод, что граф переходов между состояниями~--- гамильтонов путь: все состояния лежат на одной цепочке из \t{1 1 ... 1} в \t{3 3 ... 3}, и других переходов нет. Для того, чтобы найти расстояние между двумя произвольными состояниями, найдем позицию каждого из них в этой цепочке и посчитаем разность.

Рекурсивный процесс построения этой цепочки напоминает перечисление чисел в троичной системе счисления: сначала идут все состояния, в которых самый большой диск лежит на стержне $1$, потом на $2$, и в конце, на $3$, что можно соотнести с числами, у которых старший разряд равен $0$, $1$ или $2$. Отличие заключается в том, что если самый большой диск лежит на стержне $2$, то все младшие разряды нужно инвертировать: $0 \to 2$, $1 \to 1$, $2 \to 0$. Продолжая этот процесс со всеми дисками от самого большого к самому маленькому, мы можем получить номер состояния в цепочке в троичной системе от $0$ до $3^n-1$.

Переведя два входных состояния в их номер в троичной системе счисления, необходимо их сравнить лексикографически и вычесть меньшее из большего по модулю $998\,244\,353$.

\end{tutorial}
