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

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

HotLog


 

Произведения на отрезках

(Время: 5 сек. Память: 16 Мб Сложность: 60%)

Задан числовой массив 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.

Пусть P[i] – произведение элементов массива A на отрезке с левой границей L[i] и правой R[i]. Требуется найти одно число – сумму всех P[i], 1 ≤ i ≤ Q, взятую по модулю 231-1.

Входные данные

Входной файл INPUT.TXT содержит три числа, разделённых пробелами: N – размер массива (20 ≤ N ≤ 215, N – степень двойки), Q – количество запросов (1 ≤ Q ≤ 108) и R31[0] (0 ≤ R31[0] < 231).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – сумму всех P[i], 1 ≤ i ≤ Q, взятую по модулю 231-1.

Пример

INPUT.TXTOUTPUT.TXT
18 3 20160831895824047

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

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

P: 1.638.278.846.880 4766 76.613.593.377.628.710

Сумма всех P[i] равна 76.615.231.656.480.356, по модулю 231-1 равна 895.824.047.


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 A. Бисер
 B. Апельсины - 2
 C. Простые пары
 D. Произведения на отрезках

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483