Симметричные карты

Автор задачи: Александр Гордеев, разработчик: Константин Бац

По условию, требовалось найти количество строчек $$$A$$$, $$$B$$$ и $$$C$$$ соответствующих длин таких, что все три строчки $$$AB$$$, $$$AC$$$, $$$BC$$$ будут являются палиндромами. Для этого необходимо, чтобы символы в некоторых позициях строк совпадали. Разобьём все позиции на группы такие, что в каждой группе позиций символы должны совпадать. Тогда ответ на задачу равен $$$10 ^ m$$$, где $$$m$$$ — максимальное количество таких групп, потому что каждой группе равных цифр можно независимо назначить любое значение.

Количество групп равных позиций можно найти при помощи системы непересекающихся множеств. Дадим позициям в строчках $$$A$$$, $$$B$$$, $$$C$$$ общую нумерацию. Каждая позиция — одноэлементное множество в СНМ. Теперь по отдельности рассмотрим строчки $$$AB$$$, $$$AC$$$, $$$BC$$$ и объединим множества, в которые входят позиции, равноудаленные от концов строк. Например, $$$A_1$$$ должно совпадать с $$$B_{|B|}$$$, поэтому объединим два соответствующих этим позициям множества в СНМ.

После всех объединений количество непересекающихся множеств и будет равно числу $$$m$$$. Для получения числа $$$10 ^ m \bmod (10^9 + 7)$$$, которое требовалось найти по условию задачи, необходимо воспользоваться алгоритмом быстрого (логарифмического) возведения в степень.