Задача Segtree2k17. В среде крутых олимпиадных  гуру модно помнить наизусть решение такой задачи: Дан массив з N чисел и M запросов вида L R. На каждый такой запрос нужно вывести произведение элементов массива, имеющих индексы от L до R включительно. Так как произведение может быть весьма велико, ответ выводим по модулю  Mod 

Рассмотрим некую модификацию  этой задачи. Условие менять не будем, изменим лишь ограничения:

Поскольку в этом случае входной файл будет достаточно большим, предлагается его генерировать. Код генератора (С++) должен быть  встроен  в решение. (Аналогичный код  на языках Pascal и  Python можно зарузить тут).

const int MAXN = 1000 * 1000;
long long a[MAXN];
long long mod;

unsigned s;
unsigned getNext(){
    s ^= (s << 13);
    s ^= (s >> 17);
    s ^= (s << 5);
    return s;
}

int main() {
    unsigned n, m, seed ;
    cin >> n >> m >> mod >> seed;
    s = seed;
    for(int i = 0; i < n; i++){
        a[i] = getNext();
    }

    long long ans = 0;
    for(int i = 0; i < m; i++){
        unsigned left = getNext() % n;
        unsigned right = getNext() % n;
        if(left > right) swap(left, right);

        long long result = query(left, right);

        ans = (ans + result) % mod;
    }
}

Таким образом, входными данными будут N, M, Mod, Seed, где Seed – начальное значение для генератора. В ответе нужно вывести сумму для каждого запроса (по модулю)

Технические условия. Программа Segtree2k17  (содержащая встроенный код генератора!)  читает с устройства стандартного ввода натуральные числа N, M, Mod, Seed   seed<=232

Программа выводит на устройство стандартного вывода единственное число – сумму результатов (по модулю) на всех запросах.

Примеры

Ввод                                                           Вывод

10 15 1000000007 1                                216091399

Ввод                                                         Вывод

5000 100000 1283189389247 8932   541836623127

Ввод                                                             Вывод

1000 100 100007 7632                           47019

 

© LIKT 1998-2018