Untitled
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 . Реши на с++