Что касается динамического программирования.
Мне кажется, что следует пойти вот каким путём.

1. Трассируем до тех пор, пока у нас всё однозначно. Это требует O(1) памяти.
2. Если наткнулись на развилку с одинаковыми буквами, — дальше нам, возможно, потребуются все эти откаты-шмоткаты, зеркала-тождества...
Поэтому прекращаем маяться дурью и включаем режим препроцессинга.

Для каждой точки оставшейся подматрицы, на которой мы только что поймали развилку, находим следующее.

Во-первых, смещаем туда (0,0) — мысленно. Это чтобы дальнейшие рассуждения упростить.
Во-вторых, для каждой точки (x,y) находим её зеркальную (x',y') относительно финиша (M,N), и проверяем, что подматрицы зеркально равны: A(x,y,M,N) = A(x',y',M,N)^T.
Это удобно делать не в лоб, за O((M*N)^2), а рекуррентно, начиная от финиша, за O(M*N).
Матрицы зеркально равны, если их подматрицы без одного столбца/строки зеркально равны, и столбец равен строке.
Получаем булеву матрицу.
В-третьих, считаем мощности путей в подматрицах. Опять же, рекуррентно это делается без умножений, а сложениями — как в треугольнике Паскаля.

В-четвёртых, этот препроцессинг — только, если делать его с самого первого момента! — позволит сделать нам нумерацию и уникальных путей!
Поскольку мы сразу обнаруживаем зеркальные подматрицы, а не только развилки.

Здравствуйте, Кодт, Вы писали:

Разучился я объяснять совсем Попробую сделать это получше.
1. Введем какое-нибудь короткое обозначение количества путей из ячейки с координатами (x, y) до правого нижнего угла. D(x, y) = C(n-x + m-y — 2, n-x-1).
2. На каждом шаге алгоритма будем добавлять по одной букве к нашему ответу и хранить все возможные позиции этой буквы. То есть у нас на шаге i будет найден префикс ответа длиной i, все позиции, где может располагаться последняя буква найденного префикса вместе с количеством путей, по которым можно дойти до этой позиции по буквам префикса. Количество наших путей до ячейки (x, y) обозначим F(x, y) (та самая динамика).
3. Затем на каждом шаге мы из всех возможных позиций делаем один шаг во все возможные стороны, получаем варианты следующей буквы префикса, считаем количество вариантов для каждого продолжения нашего префикса, находим ту, которая удовлетворяет нашему порядковому номеру, обновляем F и текущее множество возможных последних букв. (И вычитаем левую границу интервала)

Попробую показать на примере:

ACAC
BCDC
CDBB
DAAA

I = 8

Шаг 1.
Result = A
Ячейки (0, 0)
F(0, 0) = 1

Шаг 2.
Два варианта AB (1, 0) и AC (0, 1). Считаем варианты:
Количество вариантов для (1, 0): F(0, 0) * D(1, 0) = 10
Количество вариантов для (0, 1): F(0, 0) * D(0, 1) = 10
Получаем, для буквы B — 10 вариантов, для С — 10 вариантов. Нам подходит B.
Result = AB
Ячейки (1, 0)
F(1, 0) = 1

Шаг 3.
Два варианта продолжения, но оба с одинаковой последней буквой — ABC (2, 0) и ABC (1, 1)
Result = ABC
Ячейки (2, 0), (1, 1)
F(2, 0) = 1, F(1, 1) = 1

Шаг 4.
Три варианта продолжения, но тоже с одинаковой буквой — ABCD (3, 0), ABCD (2, 1), ABCD (1, 2)
Result = ABCD
Ячейки (3, 0), (2, 1), (1, 2)
F(3, 0) = 1, F(2, 1) = 2, F(1, 2) = 1

Шаг 5.
Продолжением могут быть три разные ячейки, посчитаем количество вариантов:
ABCDA (3, 1): F(3, 0) * D(3, 1) + F(2, 1) * D(3, 1) = 3
ABCDB (2, 2): F(2, 1) * D(2, 2) + F(1, 2) * D(2, 2) = 6
ABCDC (1, 3): F(1, 2) * D(1, 3) = 1
Получаем вариантов заканчивающихся на A — 3, на B — 6, на C — 1. Нам нужно найти восьмую строку, поэтому нам подходит вариант буквы B.
Result = ABCDB
Ячейки (2, 2)
F(2, 2) = 3
I = 5 (вычитаем нижнюю границу)

Шаг 6.
ABCDBA (3, 2): F(2, 2) * D(3, 2) = 3
ABCDBB (3, 2): F(2, 2) * D(2, 3) = 3
Выбираем букву B
Result = ABCDBB
Ячейки (2, 3)
F(2, 3) = 3
I = 2

Шаг 7.
Ответ ABCDBBA

Здравствуйте, _DAle_, Вы писали:


_DA>Попробую показать на примере:

_DA>ACAC
_DA>BCDC
_DA>CDBB
_DA>DAAA

_DA>I = 8


_DA>Шаг 5.
_DA>Продолжением могут быть три разные ячейки, посчитаем количество вариантов:
_DA>ABCDA (3, 1): F(3, 0) * D(3, 1) + F(2, 1) * D(3, 1) = 3
_DA>ABCDB (2, 2): F(2, 1) * D(2, 2) + F(1, 2) * D(2, 2) = 6
_DA>ABCDC (1, 3): F(1, 2) * D(1, 3) = 1
_DA>Получаем вариантов заканчивающихся на A — 3, на B — 6, на C — 1. Нам нужно найти восьмую строку, поэтому нам подходит вариант буквы B.
_DA>Result = ABCDB
_DA>Ячейки (2, 2)
_DA>F(2, 2) = 3
_DA>I = 5 (вычитаем нижнюю границу)

Я так понимаю, что 8-F(2, 2) = 8-3 = 5. Но почему именно так отбрасываются пути с меньшими номерами, чем 8, почему не 8-6?

Здравствуйте, olimp_20, Вы писали:

_DA>>Шаг 5.
_DA>>Продолжением могут быть три разные ячейки, посчитаем количество вариантов:
_DA>>ABCDA (3, 1): F(3, 0) * D(3, 1) + F(2, 1) * D(3, 1) = 3
_DA>>ABCDB (2, 2): F(2, 1) * D(2, 2) + F(1, 2) * D(2, 2) = 6
_DA>>ABCDC (1, 3): F(1, 2) * D(1, 3) = 1
_DA>>Получаем вариантов заканчивающихся на A — 3, на B — 6, на C — 1. Нам нужно найти восьмую строку, поэтому нам подходит вариант буквы B.
_DA>>Result = ABCDB
_DA>>Ячейки (2, 2)
_DA>>F(2, 2) = 3
_DA>>I = 5 (вычитаем нижнюю границу)

_>Я так понимаю, что 8-F(2, 2) = 8-3 = 5. Но почему именно так отбрасываются пути с меньшими номерами, чем 8, почему не 8-6?

Потому что нам нужно найти восьмую строку. Первые три из них (в порядке возрастания) начинаются на ABCDA, они нам не подходят. Следующие шесть начинаются на ABCDB — это наш вариант, так как 3+6 >= 8. Строки, начинающиеся на ABCDA, мы просто откидываем, и ищем только среди строк, начинающихся на ABCDB, а среди этих строк наша искомая строка является пятой.

Здравствуйте, _DAle_, Вы писали:

_DA>Ты извини, конечно, но ты довольно давно задаешь вопросы в этом форуме в виде "олимпиадных" задач, тебе тут с переменным успехом помогают разобраться, но прогресса никакого не видно, если честно. Зачем ты их вообще решаешь, с какой целью, может тебе совет какой-нибудь дать?

Скорее, вам нужно дать совет — научиться различать троллей. Да, бывают и такие.

Здравствуйте, _DAle_, Вы писали:

_DA>1. Введем какое-нибудь короткое обозначение количества путей из ячейки с координатами (x, y) до правого нижнего угла. D(x, y) = C(n-x + m-y — 2, n-x-1).
_DA>2. На каждом шаге алгоритма будем добавлять по одной букве к нашему ответу и хранить все возможные позиции этой буквы. То есть у нас на шаге i будет найден префикс ответа длиной i, все позиции, где может располагаться последняя буква найденного префикса вместе с количеством путей, по которым можно дойти до этой позиции по буквам префикса. Количество наших путей до ячейки (x, y) обозначим F(x, y) (та самая динамика).

Поскольку на шаге i мы находимся на диагонали x+y=i, — можем оперировать одномерными позициями (например, иксами).
Это так, к слову.

_DA>3. Затем на каждом шаге мы из всех возможных позиций делаем один шаг во все возможные стороны, получаем варианты следующей буквы префикса, считаем количество вариантов для каждого продолжения нашего префикса, находим ту, которая удовлетворяет нашему порядковому номеру, обновляем F и текущее множество возможных последних букв. (И вычитаем левую границу интервала)

Ну, в принципе, да.
Чистая динамика, без откатов. И хранить нужно будет всего 2 фронта — диагонали — шириной до min(M,N).

Здравствуйте, _DAle_, Вы писали:

<>

А слабо — то же самое, но для уникальных текстов?

Здравствуйте, Кодт, Вы писали:

К>А слабо — то же самое, но для уникальных текстов?

Похоже, слабо. Как-то мрачновато задачка выглядит.