Условие:
Ограничение по времени: 1.5 секунд
Ограничение по памяти: 512 мегабайт
Имеется рекуррентная последовательность A1, A2, …, AN, строящаяся по следующему правилу:
A1 = K
Ai+1 = (Ai × M) % (232 – 1) % L
Требуется найти сумму всех нечетных по порядку элементов в отсортированной по неубыванию последовательности по модулю L.
Для входных данных
5 7 13 100
последовательность будет такой:
{7; 7 × 13%100 = 91; 91 × 13%100 = 83; 83 × 13%100 = 79; 79 × 13%100 = 27}, то есть {10; 91; 83; 79; 27}.
Отсортированная последовательность {7; 27; 79; 83; 91}.
Сумма элементов на нечетных местах = (7 + 79 + 91)%100 = 77.
Формат входных данных:
N K M L
5000000 ≤ N ≤ 60000000, 0 ≤ K, L, M ≤ 232 – 1
Формат выходных данных:
RESULT
Примеры:
Стандартный ввод Стандартный вывод
5 7 13 100 77
Замечание. Для представления элементов последовательности необходимо использовать тип данных unsigned int.
Для получения массива используйте цикл:
a[0] = K;
for (int i = 0; i < N-1; i++)
a[i+1] = (unsigned int) ((a[i]*unsigned long long)M)&0xFFFFFFFFU)%L;
Внимание! Изменение типа данных и/или метода генерации элементов массива может привести (и на различных компиляторах приводит) к другой последовательности!
Решение:
Для решения задачи, давайте разберем шаги, которые нам нужно выполнить. 1. Построение последовательности: Мы будем использовать формулу для генерации элементов последовательности. Начнем с первого элемента A1 = K и будем вычислять последующие элементы по формуле Ai+1 = (Ai × M) % (232 - 1) % L. 2. Сохранение элементов: Поскольку N может быть очень большим (до 60 миллионов), мы не можем хранить все элементы в памяти. Вместо этого мы будем использовать подход, который позволяет нам не хранить всю последовательность, а только необходимые значения. 3. Сортировка: После генерации всех элементов ...
Теперь давайте разберем, как работает этот код: 1. Мы создаем пустой список , в который будем добавлять элементы последовательности. 2. С помощью цикла мы генерируем N элементов последовательности, используя заданную формулу. 3. После генерации всех элементов мы сортируем список . 4. Затем мы проходим по элементам с нечетными индексами (0, 2, 4 и т.д.) и суммируем их, применяя модуль L. 5. В конце мы возвращаем результат. Теперь, если мы введем данные , программа вернет , что соответствует ожидаемому результату.