| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 2 | 1 | 1 | 50.000% |
Назовем две строки $s$ и $t$ эквивалентными, если для любой строки $u$ длины 2ドル,ドル количество вхождений $u$ в $s$ совпадает с количеством вхождением $u$ в $t$. Таким образом, строки «aaaba», «abaaa» и «baaab» попарно эквивалентны между собой (строка «aa» входит два раза, строка «ab» один раз, строка «ba» один раз, строка «bb» не входит как подстрока), а строки «abb» и «bba» — нет.
В этой задаче вам будут даны $Q$ строк, состоящих из символов «a», «b» и «c», для каждой из которых надо будет посчитать количество эквивалентных им непустых строк, также состоящих из символов «a», «b» и «c». Так как это количество может быть очень большим, то надо вывести его остаток при делении на 10ドル^9 + 7$.
В первой строке входных данных дано число $G$ — номер подзадачи, к которой относится текущий тест. Для теста из примера $G = 0$.
На второй строке дано число $q$ (1ドル \le q \le 10^5$), затем следуют $q$ строк, состоящих из символов «a», «b» и «c». Суммарная длина строк не превышает 10ドル^6$.
Требуется вывести $q$ целых чисел — для каждой строки необходимо вывести количество эквивалентных ей по модулю 10ドル^9 + 7$.
За $n_i$ обозначена длина $i$-й строки во входных данных, за $L$ обозначена сумма длин строк, за $w$ – максимальный ответ (не взятый по модулю) среди всех запросов.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | строка $s$ не содержит символов « |
| 2 | 13 | символы « |
| 3 | 11 | $n_i \le 13$ |
| 4 | 10 | $L \le 40$ |
| 5 | 9 | $L \le 60$ |
| 6 | 13 | $w \le 100$; $L \le 10^5$ |
| 7 | 33 | нет |
0 4 abaa abca ccbca bacc
3 3 2 1
Строке «abaa» эквивалентны строки «abaa», «aaba», «baab»;
Строке «abca» эквивалентны строки «abca», «bcab», «cabc»;
Строке «ccbca» эквивалентны строки «ccbca» и «cbcca»;
Строке «bacc» эквивалентна только строка «bacc».
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2023 8번