Здравствуйте, ребята!
Вот задачка:
После многих лет безуспешных попыток ученые наконец-то смогли установить связь с разумной цивилизацией в космосе и выяснили, что алфавит инопланетян состоит всего из двух букв: a и b. Для приема сообщений был сконструирован специальный приемник, который выдает символы a, b, а также специальный символ ?, если разобрать, какой символ был передан, не удалось.
Анализ показал, что инопланетяне передают все свои сообщения в виде двух одинаковых записанных подряд строк. Например, строки «abab» или «aaaaaa» могут быть сообщениями инопланетян, а «abba» или «aaa» — нет.
Прибор, сконструированный учеными, получив на вход потенциальное сообщение инопланетян, выдает все возможные способы прочитать строку без учета описанного выше свойства. Например, получив строку «ab??» прибор выдает строки «abaa», «abab», «abba» и «abbb», из них на самом деле только строка «abab» может быть сообщением от инопланетян, а остальные три не могут.
Для улучшения качества прибора ученые хотят узнать, сколько строк из тех, которые выведены прибором, не могут быть сообщением инопланетян. Помогите им это сделать.
Формат входных данных
В первой строке содержится натуральное число n — число слов в сообщении, полученного учеными.
В каждой из следующих n строк содержится слово из сообщения, состоящее из символов a, b и ?. Гарантируется, что все слова имеет четную длину, а также, что в каждом слове есть хотя бы один ?. Суммарная длина всех слов не превышает 200000. Не гарантируется, что есть хотя бы один способ расшифровать каждое слово как сообщение инопланетян.
Формат выходных данных
Выведите n строк. В i-ой строке выведите число способов заменить ? на буквы a, b так, чтобы i-е слово не было корректным сообщением инопланетян. Так как число способов может быть очень большим, необходимо выводить его по модулю 10^9+7.
Примеры
Входные данные
3 ab?b baa? abb???Выходные данные
1 2 7
А вот предлагаемый алгоритм решения:
Заметим, что ответ равен числу всех возможных сообщений, минус число тандемных повторов. Обозначим за m число вопросов в строке, а за 2l длину строки. Тогда количество всех возможных сообщений равно 2^m. Число тандемных повторов можно найти из следующих рассуждений. Если на позиции i стоит знак вопроса, а на позиции i + l a или b, то в тандемном повторе, на позиции i должна стоять та же буква. Если же на обеих позициях i и i + l стоят знаки вопроса, то ответ нужно домножить на два. Аналогично рассматривается ситуация, когда знак вопроса стоит на позиции i + l. Если на позициях i и i + l стоят различные буквы, то тандемных повторов для такой строки не существует.
Время работы O(длины сообщения).
Вопрос: является ли описываемый алгоритм правильным решением?
