Есть N ≤ 1018 пар (Pi, Wi) сгенерированных по следующему алгоритму:
- Pi = ((A*Pi-1 + B) mod M) + 1
- Wi = ((C*Wi-1 + D) mod K) + 1
- Где M, K ≤ 107, P1, W1, A, B, C, D заданы.
- Требуется найти:
- Количество пар (Pi, Wi) таких что не существует пары (Pj, Wj) такой что Pj ≤ Pi и Wj < Wi либо Pj < Pi и Wj ≤ Wi
- Количество пар (Pi, Wi) таких что не существует пары (Pj, Wj) такой что Pj ≥ Pi и Wj > Wi либо Pj > Pi и Wj ≥ Wi
Разберемся с первой частью, вторая делается аналогично.
Заметим, что если все Pi одинаковы, то ответ это количество минимумов.
Переходим к двумерной задаче: для каждого P < M будем хранить текущий минимум minp и количество найденных пар вида (P, minp).
Если посчитать эти величины, то ответ ищется просто: для каждого p надо проверить что нет такого p0 < p что minp0 ≤ minp , и в этом случае прибавить к ответу количество пар вида (P, minp). Это делается за один проход.
Как же искать этот minp ?
Понятно, что через max(M, K) элементов обе последовательности зациклятся. Обработаем этот кусок, выкинем его и рассмотрим циклы, осталось обработать N1 = N - max(M, K) пар.
Получившиеся циклы:
p0, p1, p2, p3, ... pA - 1
w0, w1, w2, w3, ... wB - 1
Для фиксированного pi важно знать минимум и количеством минимумов тех w, что попадают в пару вместе с фиксированным pi:
Для p0 они имеют индексы 0, A%B, (2 * A)%B, ...
Для p1 это 1, (A + 1)%B, (2 * A + 1)%B, ...
Для p2 это 2, (A + 2)%B, (2 * A + 2)%B, ...
Для p(A - 1) это (A - 1)%B, (2 * A - 1)%B, ...
Все индексы меньше N1
Вот тут можно поступить по-разному
- Разбить цикл из w на орбиты элементов которые идут через A и на каждой использовать RMQ. Это O(max(M, K) * logN) по времени. Можно улучшить до O( max(M, K) ) используя RMQ за O(1) два раза, ведь последовательности могут иметь длины ⌈ N1 / A⌉ и ⌊ N1 / A⌋.
- Cчитать минимум и количество минимумов среди элементов w проиндексированных (i + j * A)%B , 0 ≤ j < 2k для каждого k, и использовать на этом двоичный подъём, "перемножая" массив как при быстром возведении в степень. Это O(max(M, K) * logN) по времени
В обоих случаях получается и и O(max(M, K)) по памяти.
Лично я выбрал второе, макстест на Java работал за 17 секунд, но на их 20 тестах программа уложилась в 2 минуты. К тому же можно было запускать это сразу на нескольких компах/ядрах.
Если вы считаете что можете объяснить это лучше и проще, пожалуйста, оставьте свои объяснения в комментариях.
Comments (0)
