Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии ограничения на $$$k$$$ и $$$q$$$ ниже. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Определим $$$\mathrm{popcount}_k(m)$$$ как сумму всех цифр числа $$$m$$$ в системе счисления по основанию $$$k$$$.
Определим бесконечное число $$$s=\overline{s_1s_2\cdots}$$$ в системе счисления по основанию $$$k$$$, где $$$i$$$-я цифра числа $$$s$$$ равна $$$s_i=(\mathrm{popcount}_k(i) \bmod k)$$$.
Дано $$$q$$$ запросов. Каждый запрос состоит из трёх целых чисел $$$l$$$, $$$r$$$ и $$$n$$$ (все они заданы в десятичной записи), а также числа $$$t$$$ из $$$n$$$ цифр в системе счисления по основанию $$$k$$$. Обратите внимание, что $$$t$$$ может содержать ведущие нули. Рассматривая $$$t$$$ как строку, требуется определить количество вхождений $$$t$$$ в строку $$$s_ls_{l+1}\ldots s_r$$$.
Для обозначения цифр, десятичное значение которых не меньше $$$\mathtt{10}$$$, используются прописные и строчные латинские буквы. В частности, прописные буквы $$$\{\mathtt{A, B,\ldots,Z}\}$$$ обозначают значения $$$\{\mathtt{10, 11,\ldots,35}\}$$$, а строчные буквы $$$\{\mathtt{a, b,\ldots,z}\}$$$ — значения $$$\{\mathtt{36, 37,\ldots,61}\}$$$.
В первой строке входных данных даны два целых числа $$$k$$$ и $$$q$$$ ($$$2\le k\le 10$$$, $$$1\le q\le 1000$$$) — основание системы счисления и количество запросов.
Каждый запрос содержит две строки. В первой строке даны три целых числа $$$l$$$, $$$r$$$ и $$$n$$$ ($$$1\le l\le r\le 10^{17}$$$, $$$1\le n\le 2\cdot 10^6$$$).
Во второй строке дано число $$$t$$$ в системе счисления по основанию $$$k$$$ с $$$n$$$ цифрами ($$$t_i\in\{\mathtt{0,1,\ldots,9,A,B,\ldots,Z,a,b,\ldots,z}\}$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^6$$$.
Для каждого запроса выведите одно целое число — ответ на запрос.
3 45 17 32015 17 2011239 1231231209 501201123002 231203 41202
2 3 21046666 8325
10 31 20 912345678915 20332 36781234 56789 201
2 1625 5000
Обозначим подстроку $$$s_ls_{l+1}\ldots s_r$$$ как $$$s[l;r]$$$.
В первом примере $$$k = 3$$$, $$$s = \mathtt{12120201120201012201120012\ldots}$$$, $$$s[5;17] = \mathtt{0201120201012}$$$, и $$$t = \mathtt{201}$$$ встречается всего $$$2$$$ раза в $$$s[5; 17]$$$. Его индексы в строке $$$s$$$ — $$$s[6; 8]$$$ и $$$s[12; 14]$$$. А $$$t = \mathtt{01}$$$ встречается $$$3$$$ раза. Его индексы в строке $$$s$$$ — $$$s[7;8]$$$, $$$s[13;14]$$$ и $$$s[15;16]$$$.
Во втором примере $$$k=10$$$, $$$s[1;20] = \mathtt{12345678912345678902}$$$, и $$$t = \mathtt{123456789}$$$ встречается всего $$$2$$$ раза в $$$s[1;20]$$$.
| Codeforces Round 1112 (Div. 1) |
|---|
| Закончено |
