АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1649. Инверсии-2

Ограничение времени: 2 сек.
Ограничение памяти:307200 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Дана последовательность целых чисел. Инверсией назовём такую ситуацию, когда большее число стоит впереди меньшего.
Например, в последовательности 4 3 2 5 1 всего 7 инверсий: 4 и 3, 4 и 2, 4 и 1, 3 и 2, 3 и 1, 2 и 1, 5 и 1.
Требуется определить количество инверсий в последовательности.


Входная последовательность определяется следующим образом: задаётся количество элементов N, первый член a1, а также параметры P и Q. Каждый следующий член последовательности вычисляется по формуле:

ai = (P * ai-1 + Q) mod 231

Исходные данные

Четыре целых числа N, a1, P и Q.
Ограничения: 1 ≤ N ≤ 107, 0 ≤ a1, P, Q < 231.

Результат

Выведите одно целое число - количество инверсий.

Пример

Исходные данныеРезультат
5 3 64525 1013904223 2

Комментарии

Пояснение к примеру: входные данные задают последовательность 3 1014097798 1847565613 1925331624 1107906023

Примечание: в данной задаче разрешается использовать многопоточность, вам доступно 4 процессора.

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Сортировка и поиск /
1651. Закраска прямой - 2 1649. 293. Построение пирамиды
 
время генерации 0.093 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.