Есть 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 минуты. К тому же можно было запускать это сразу на нескольких компах/ядрах.
Если вы считаете что можете объяснить это лучше и проще, пожалуйста, оставьте свои объяснения в комментариях.
А, это просто.
-xmx2048M помог.
Если бы у нас N1 делилось на НОК(A,B), то в W было бы НОД(A,B) орбит элементов через А, и в P было бы НОД(A,B) орбит элементов через В. При этом если пронумеровать орбиты по их первому элементу, то все элементы из орбиты i в P встречались бы в паре со всеми элементами из орбиты i в W.
Тогда берём минимум в первой, минимум во второй - и это пара кандидат на минимальную. Т.е. всего будет НОД(A,B) кандидатов. А что делать если N1 не делится на НОК ? Я написал какой-то изврат: поочередно то в одном то в другом массиве выбираю минимальный не вычеркнутый элемент, просматриваю всех кто с ним в паре во втором массиве, запоминаю минимум и вычеркиваю все просмотренные. Потом с помощью Фенвика проверяю является ли эта пара кандидатом на ответ (Пока писал это предложение понял, ночью голова не варила... Зачем было ещё Фенвика прикручивать, если потом я всё равно буду проверять можно ли посчитать эту пару как хорошую). В общем в итоге я разбил всё на три части - найти пары для хвоста, для нока, и для N1 % НОК. Но после этого я как последний баран их пихал в массив на 30 лимонов из пар интов и сортил его)) В итоге оно сумело пройти всего 4 теста, примерно по минуте с лишним на тест. Можно поподробней как посчитать для N1 ответ не разбивая на НОК и остаток от НОКа за O(max(M, K) * logN)?
Да, берём две соответствующие орбиты: пусть одна P (берутся элементы из первого цикла идущие через B и соотв. ей из W (берутся элементы из второго цикла через A).
Вы имеете ввиду элементы подряд из соответствующей орбиты? И под подряд понимается циклически подряд?