Суммы на отрезках - 2
(Время: 3 сек. Память: 16 Мб Сложность: 40%)
Задан числовой массив A[1..N]. Необходимо выполнить Q операций вычисления суммы на отрезке [L, R].
Содержимое массива и параметры запросов будем получать из последовательности псевдослучайных чисел.
Последовательность 31-битных псевдослучайных чисел R31 определена следующим образом: R31[0] задано во входных данных, последующие значения вычисляются по формуле:
R31[i+1] = (R31[i]*1103515245+12345) mod 231, i ≥ 0, где mod - операция остатка от деления.
Последовательность 15-битных псевдослучайных чисел R15 определена следующим образом:
R15[i] = R31[i] div 216, i ≥ 0, где div - операция целочисленного деления.
Сначала из R15 заполняются элементы массива:
A[i]=R15[i], 1 ≤ i ≤ N.
Затем из R15 извлекаются пары границ. Для того чтобы границы попадали в диапазон индексов массива, числа обрабатываются следующим образом:
B[i] = (R15[N+i] mod N) + 1, 1 ≤ i ≤ 2Q.
В каждой паре минимальное из чисел становится левой границей, а максимальное – правой:
L[i] = min(B[2i–1],B[2i]), R[i] = max(B[2i–1],B[2i]), 1 ≤ i ≤ Q.
Пусть S[i] – сумма элементов массива A на отрезке с левой границей L[i] и правой R[i]. Требуется найти одно число – сумму всех S[i], 1 ≤ i ≤ Q, взятую по модулю 231.
Входные данные
Входной файл INPUT.TXT содержит три числа, разделённых пробелами: N – размер массива (20 ≤ N ≤ 215, N – степень двойки), Q – количество запросов (1 ≤ Q ≤ 108) и R31[0] (0 ≤ R31[0] < 231).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – сумму всех S[i], 1 ≤ i ≤ Q, взятую по модулю 231.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 8 3 20160831 | 121158 |
Пояснение к примеру
R31: 1943472652 686235477 649227626 1632309851 435206904 2017942481 151123510 312375607 1844612772 781509645 1643069378 710373843 1209790736 968406025
R15: 29655 10471 9906 24907 6640 30791 2305 4766 28146 11924 25071 10839 18459 14776
A: 29655 10471 9906 24907 6640 30791 2305 4766
B: 3 5 8 8 4 1
L: 3 8 1
R: 5 8 4
S: 41453 4766 74939
Сумма всех S[i] равна 121158, по модулю 231 значение такое же.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|