printРабочее место участника

printЗадачи

2355. Фуршет

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Маша знает 26 рецептов закусок, которые она обозначает буквами от a до z. Для фуршета она приготовила несколько закусок, выбирая перед началом приготовления очередной закуски совершенно случайным образом один из 26 рецептов, и расставила их на круглом столе в порядке приготовления.
Пришедшие гости подходят к любой точке стола и, двигаясь по часовой или против часовой стрелки, пробуют от 1 до `N` закусок подряд.
Напишите программу, которая определит количество вариантов проб длиной не более `N`, которые могут сделать гости, если пробы считаются одинаковыми, когда они имеют одинаковую длину и одинаковые рецепты закусок в тех же позициях.
Первая строка ввода содержит `N` (`2\ ≤\ N\ ≤\ 100000`). Вторая строка ввода содержит последовательность из строчных латинских букв длиной от 2 до 50000 – порядок приготовления закусок, полученный указанным выше способом.
Вывести одно целое число – количество вариантов проб.

Пример ввода 1

3
ab

Вывод для примера 1

6

Пример ввода 2

3
erjej

Вывод для примера 2

17
Пояснение к примеру 1: возможны следующие пробы a, b, ab, ba, aba, bab.
Пояснение к примеру 2: возможны следующие пробы e, r, j, er, re, rj, jr, je, ej, erj, jre, rje, ejr, jej, eje, jer, rej.
loading