Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
8.1 kB
2
Indexable
Never
Недавно Кузя разбирал чердак на даче своей бабушки и нашел очень древнюю и непонятную книгу. Кузя сразу понял, что это книга с заклинаниями, а бабушка — волшебница, просто это скрывает.
А раз бабушка умеет творить магию, то и Кузя сможет! Кузя решил тут же применить свои недюжинные навыки чтения и прочитать какие-нибудь заклинания из книги.
В дальнейшем будем считать, что все записи в книге представляют собой одну большую строку
S
. Все символы в книге представляют собой малые латинские буквы.
Кузя смотрел много фильмов про волшебников, поэтому знает два важных правила:

Если в данный момент прочитан символ на позиции
i
, то следующим Кузя должен прочитать символ на позиции
p
i
;
Пусть
k
i
— порядковый номер в алфавите символа на
i
-й позиции в тексте (
a
—
0
-й,
z
—
2
5
-й). Если Кузя за время одного заклинания должен прочитать символ на
i
-й позиции в
m
i
-й раз, то вместо этого он вслух произносит символ с порядковым номером в алфавите
(
k
i
+
(
m
i
−
1
)
⋅
d
i
)
mod
2
6
.
Подробный пример находится в примечании к тестовым примерам (в самом низу).
Обратите внимание, что изменения символов при прочтении действуют только в рамках одного заклинания (
m
i
считаются независимо для каждого прочтения заклинания).
Кузя считает, что сила прочитанного заклинания равна количеству уникальных символов, которые в него вошли. К примеру, в заклинании «
z
b
a
c
b
e
f
» ровно
6
уникальных символов
[
a
,
b
,
c
,
e
,
f
,
z
]
.
Кузя нашел на обложке книги число
K
и понял, что для оптимального эффекта необходимо прочесть заклинания всех длин от
1
до
K
включительно, начав по очереди с каждого символа от
1
до
N
(всего Кузя планирует прочесть
N
×
K
заклинаний).
Кузя боится слишком мощных выбросов магической энергии. Поэтому он просит вас, как победителя викторины по Гарри Поттеру в
5
-м классе, заранее вычислить суммарную силу всех
N
×
K
заклинаний, которые он собирается прочесть.

Формат ввода
В первой строке дано два целых числа
N
и
K
(
1
≤
N
≤
1
0
5
,
1
≤
K
≤
1
0
9
)
— количество символов в тексте книги.
Во второй строке дана строка
S
длины
N
, состоящая из малых латинских букв
(
S
i
∈
[
a
…
z
]
)
— текст книги с заклинаниями.
В третьей строке дано
N
целых чисел
p
i
через пробел
(
1
≤
p
i
≤
N
)
— позиция символа, который следует прочесть после чтения символа на
i
-й позиции.
В четвертой строке дано
N
целых чисел
d
i
через пробел
(
0
≤
d
i
≤
2
5
)
— сдвиг при повторном чтении символа на
i
-й позиции (читайте условие и примечание).

Формат вывода
В единственной строке выведите единственное число — суммарную силу всех
N
×
K
заклинаний, начинающихся в каждой из позиций
1
,
2
,
…
,
N
и имеющих длину
1
,
2
,
…
,
K
.

Пример 1
Ввод
3 7
abz
3 1 2
4 0 3

Вывод
74

Примечания
Пояснение к первому тестовому примеру.
Текст в книге равен строке
S
=
«
a
b
z
»;
Массив
p
равен
[
3
,
1
,
2
]
;
Массив
d
равен
[
4
,
0
,
3
]
;
Разберем детально чтение одного из заклинаний: пусть Кузя начнёт читать заклинание с позиции
3
в тексте и прочтёт
7
символов. В таком случае он прочтёт строку «
z
b
a
c
b
e
f
»:

Символ на
3
-й позиции равен
z
. Кузя читает его в
m
3
=
1
-й раз, поэтому он читает символ
z
без изменений. После этого Кузя должен прочесть символ на позиции
p
3
=
2
;
Аналогично Кузя читает символ
b
на
2
-й позиции в
m
2
=
1
-й раз, поэтому он читает именно символ
b
и переходит к символу
p
2
=
1
;
Далее Кузя читает символ
a
на
1
-й позиции в
m
1
=
1
-й раз, поэтому он читает символ
a
без изменений и переходит к символу
p
1
=
3
;
Кузя читает символ на позиции
3
, но уже в
m
3
=
2
-й раз. Из этого следует, что на самом деле Кузя должен произнести не
z
(
2
5
-й в алфавите), а
(
2
5
+
(
2
−
1
)
⋅
3
)
mod
2
6
=
2
-й символ в алфавите - это символ
c
. После чего Кузя снова должен перейти к символу на позиции
p
3
=
2
;
Так как
d
2
=
0
, то на
2
-й позиции Кузя будет всегда читать один и тот же символ
b
;
А вот вместо символа
a
(
0
-й в алфавите) на позиции
1
Кузя в
m
1
=
2
-й раз прочтёт символ
(
0
+
(
2
−
1
)
⋅
4
)
mod
2
6
=
4
-й символ в алфавите —
символ
e
;
Завершает Кузя чтением символа на позиции
3
в
m
3
=
3
-й раз, поэтому в этот раз он прочтёт
(
2
5
+
(
3
−
1
)
⋅
3
)
mod
2
6
=
5
-й символ в алфавите - это символ
f
.
Список всех заклинаний, которые Кузя прочтёт:
Начиная с позиции
1
:

a
— сила
1
;
a
z
— сила
2
;
a
z
b
— сила
3
;
a
z
b
e
— сила
4
;
a
z
b
e
c
— сила
5
;
a
z
b
e
c
b
— сила
5
(символ
b
уже встречался ранее, поэтому не увеличивает силу);
a
z
b
e
c
b
i
— сила
6
(
i
получился как
4
-й символ после
e
).
Начиная с позиции
2
:

b
— сила
1
;
b
a
— сила
2
;
b
a
z
— сила
3
;
b
a
z
b
— сила
3
;
b
a
z
b
e
— сила
4
;
b
a
z
b
e
c
— сила
5
;
b
a
z
b
e
c
b
— сила
5
.
Начиная с позиции
3
(подробно описаны выше):

z
— сила
1
;
z
b
— сила
2
;
z
b
a
— сила
3
;
z
b
a
c
— сила
4
;
z
b
a
c
b
— сила
4
;
z
b
a
c
b
e
— сила
5
;
z
b
a
c
b
e
f
— сила
6
.
Суммарная сила всех прочтённых заклинаний равна
7
4
.

Реши на с++