403 / 261 / 167
Регистрация: 13.01.2021
Сообщений: 1,162
|
|
1 | |
Маленький Слоник22.05.2022, 13:42. Показов 250. Ответов 0
Метки нет (Все метки)
Маленький Слоник нашел на чердаке старую потрепанную черно-белую строку s.
Символы строки s пронумерованы слева направо от 1 до |s|, где |s| — длина строки. Обозначим i-тый символ строки si. Так как строка черно-белая, каждый символ строки это либо буква «B», либо буква «W». К сожалению, строка очень старая и некоторые символы повреждены. На их позициях стоит буква «X». Маленький Слоник намерен восстановить строку и повесить ее себе на стену. Для этого нужно каждый символ «X» заменить на «B» или «W». Чтобы строка хорошо смотрелась на стене, нужно чтобы она была красивой. Маленький Слоник считает строку красивой, если у нее есть две непересекающиеся подстроки, заданной длины k, таких, что левая полностью состоит из символов «B», а правая полностью состоит из символов «W». Более формально, существует четыре целых числа a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ |s|; b - a + 1 = d - c + 1 = k) таких, что si = «B» (a ≤ i ≤ b) и sj = «W» (c ≤ j ≤ d). Помогите Маленькому Слонику найти количество различных красивых строк, которые он может получить из строки s. Две строки считаются различными, если существует такая позиция, в которой символ в первой строке отличается от соответствующего символа второй строки. Если в строке нет символов «X» и она уже красивая — то ответ 1. Так как ответ может быть довольно большим, выведите его остаток от деления на 1000000007 (109 + 7). Входные данные В первой строке через пробел заданы два целых числа n и k (1 ≤ k ≤ n ≤ 106). Во второй строке задана строка s. Строка s имеет длину n и состоит только из символов «W», «B» и «X». Выходные данные В единственной строке выведите целое число — ответ на задачу по модулю 1000000007 (109 + 7).
0
|
22.05.2022, 13:42 | |
Ответы с готовыми решениями:
0
Маленький вопросик маленький вопросик Маленький калькулятор маленький простенький вопросик... Проверьте маленький код |
22.05.2022, 13:42 | |
22.05.2022, 13:42 | |
Помогаю со студенческими работами здесь
1
Маленький (команд на 10) интерпретатор на C++ Нужно маленький ответ) перевести маленький код с Pascal на C++ Продолжаем писать маленький интерпретатор Переведите маленький код с питон на C++ Маленький косяк с шаблоном класса Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |