Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Суммы на отрезках - 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.TXTOUTPUT.TXT
18 3 20160831121158

Пояснение к примеру

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 значение такое же.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Статические RSQ и RMQ
 Sqrt-декомпозиция
 Дерево Фенвика
 Дерево отрезков
 A. Простые операции над массивом
 B. Суммы на отрезках
 C. Суммы в прямоугольнике
 D. Прямоугольник
 E. Суммы на отрезках - 2
 F. Произведения на отрезках
 G. Минимумы на отрезках
 H. Минимумы на отрезках - 2
 I. Охрана
 J. Минимумы в прямоугольнике
 K. Пирамида

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru