Codeforces Round 770 (Div. 2) |
---|
Закончено |
Вам дана строка $$$s$$$ длины $$$n$$$ и число $$$k$$$. Обозначим за $$$rev(s)$$$ развёрнутую строку $$$s$$$ (т.е. $$$rev(s) = s_n s_{n-1} ... s_1$$$). Вы можете выполнять два типа операций:
После выполнения ровно $$$k$$$ операций (возможно, различных) над строкой, какое количество различных строк вы можете получить из начальной строки $$$s$$$?
Мы обозначили конкатенацию строк $$$s$$$ и $$$t$$$ как $$$s + t$$$. Другими словами, $$$s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m$$$, где $$$n$$$ и $$$m$$$ - длины строк $$$s$$$ и $$$t$$$ соответственно.
Первая строка содержит число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.
В следующих $$$2 \cdot t$$$ строках вводится $$$t$$$ наборов входных данных:
Первая строка каждого набора содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le 1000$$$).
Вторая строка каждого набора содержит одну строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.
Для каждого набора входных данных в отдельной строке выведите количество различных строк, которые вы можете получить после применения ровно $$$k$$$ операций.
Можно показать, что при данных ограничениях ответ не превосходит $$$10^9$$$.
4 3 2 aab 3 3 aab 7 1 abacaba 2 0 ab
2 2 1 1
Рассмотрим первый набор входных данных:
После первой операции строка $$$s$$$ может стать либо aabbaa, либо baaaab. После второй операции $$$s$$$ может принимать только такие 2 значения: aabbaaaabbaa и baaaabbaaaab.
Название |
---|