Строки Фибоначчи
(Время: 1 сек. Память: 16 Мб Сложность: 48%)
Строку Фибоначчи F(K) для натуральных чисел K определим так:
F(1) = 'A', F(2) = 'B',
F(K) = F(K-1) + F(K-2) при K > 2, где "+" означает конкатенацию строк.
Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F(N).
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 45), во второй строке записана не пустая строка S, состоящая не более, чем из 25 символов A и B.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - количество вхождений строки S в строку Фибоначчи F(N).
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 1 A | 1 |
2 | 2 ABA | 0 |
3 | 8 BBABAB | 3 |
4 | 35 BBABAB | 1346268 |
Примечание
Длина строки F(45) равна 1 134 903 170.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|