ОЛИМПИАДА ПО ИНФОРМАТИКЕ

Question

ОЛИМПИАДА ПО ИНФОРМАТИКЕ

Алина Осипова Знаток (296), на голосовании 6 месяцев назад

Прямоугольник
2 × n
разделен на доминошки
2 × 1
. Доминошки нужно раскрасить в три цвета: красный, синий и зеленый так, чтобы соседние по стороне доминошки были разных цветов.

Например, такая раскраска правильная.

А такая раскраска — неправильная, потому что две красные доминошки соседние.

Посчитайте, сколько есть способов покрасить доминошки таким образом.

Входные данные
Первая строка содержит число
n
(
1
≤
n
≤
52
). Следующие две строки по
n
символов каждая описывают разбиение на доминошки. Каждая строка состоит из больших и маленьких английских букв, одинаковые символы соответствуют клеткам одной доминошки.

Выходные данные
Выведите одно число — число правильных раскрасок доминошек.

Примеры
ВХОДНЫЕ ДАННЫЕ
3
aab
ccb
ВЫХОДНЫЕ ДАННЫЕ
6
ВХОДНЫЕ ДАННЫЕ
1
Z
Z
ВЫХОДНЫЕ ДАННЫЕ
3
ВХОДНЫЕ ДАННЫЕ
52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn
ВЫХОДНЫЕ ДАННЫЕ
30958682112
Примечание
Вот все 6 способов раскрасить доминошки в первом примере.

Answer 1

Ну смотри. Если сделать ротацию раскраски по цепочки где R->G G->B B->R. То мыв первом вариант получим 3 варианта. Для одной схемы.
Далее нам надо посчитать кол-во возможных схем:
Есть вариант цепь таких фигур:
ВГГ-ВГГ-ВГГ...(вертикальная-2горизонтальные)
ГГВ-ГГВ-ГГВ...
ВГГГГ-ВГГГГ...(как на рисунке)
ГГГГВ-ГГГГВ...
ГГГГГГ-ГГГГГГ...
ВВВ-ВВВ...
больше не придумал схем
То есть цепь состоит из 3 или 4 фигур
и смотрим по остатку от деления на 3 и 4.

Ну и посчитай для каждой схемы:
А затем варианты для каждой схемы нужно сложить и вуаля