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

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

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