Кошма Туэ — Морса


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Войлочную кошму из Нарына выкладывают из полосок двух цветов: светлых (0) и тёмных (1). Мастер раскладывает полоски по последовательности Туэ — Морса:

  • t[0] = 0;
  • t[2i] = t[i], t[2i + 1] = 1 − t[i].

Получается 0110100110010110…: каждый следующий блок длины 2^k — это предыдущий блок с заменой цветов. Эта последовательность нигде не содержит трёх одинаковых блоков подряд, поэтому узор не надоедает глазу.

Рисунок

Покупатель хочет найти на кошме любимый рисунок — строку s из нулей и единиц. Сколько раз s встречается (вхождения могут перекрываться) среди первых N полосок t[0], t[1], …, t[N − 1]?

Входные данные

В первой строке — число q (1 ≤ q ≤ 500). В каждой из следующих q строк — целое число N и строка s через пробел (1 ≤ N ≤ 10¹⁸, 1 ≤ |s| ≤ 40, s состоит из символов 0 и 1).

Выходные данные

Для каждого запроса выведите количество позиций i (0 ≤ i ≤ N − |s|), для которых t[i] t[i+1] … t[i+|s|−1] = s.

Пример 1

Вход:

4
16 11
16 000
16 0110
1000 1

Выход:

3
0
3
500

Пояснение

Первые 16 полосок: 0110100110010110. Строка 11 встречается в них 3 раза (с позиций 1, 5 и 11). Строки 000 в последовательности нет вообще.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов N ≤ 2 · 10⁵.


Комментарии

Еще нет ни одного комментария.