Ёлка для енота В стране енотов есть n городов, расположенных в ряд. Еноты любят гигантские ёлки, каждую из которых они устанавливают так, что она накрывает города с номерами в отрезке чётной длины от l до r включительно.
Ёлочным треугольником последовательности b1, ..., bk чётной длины назовём набор последовательностей Ti. Первая последовательность совпадает с данной (T1 = b1, ..., bk), а каждая из оставшихся получена удалением первого и последнего элемента из предыдущей (Ti = bi, ..., bk - i + 1). Например, ёлочный треугольник последовательности 1, 2, 3, 4, 5, 6 выглядит так:
Ёлкой последовательности c1, ..., ck чётной длины называется последовательность ёлочных треугольников последовательностей S1, ..., Sk/2, где Si = ci, ..., ck - i + 1. При этом центр каждого треугольника совпадает с центром ёлки. Например, ёлка последовательности 1, 2, 3, 4, 5, 6 выглядит так:
В каждом городе есть свой вид украшений: в i-м городе красота украшений равна ai. Когда еноты устанавливают гигантскую ёлку, накрывающую города с номерами в отрезке [l, r], то каждый город под этой ёлкой вешает свои украшения на все позиции в ёлке, под которыми этот город находится. Например, если накрыто шесть городов, то четвёртый накрытый город вешает украшения на все позиции, обозначенные четвёркой на рисунке выше.
Красота ёлки - сумма значений красоты каждого использованного украшения.
Вам даны значения красоты украшений, используемых в каждом городе, и описания k гигантских ёлок, которые ставили еноты. Енот Дмитрий хочет работать аналитиком, и в качестве тестового задания ему предложили упорядочить данный вам список из ёлок по возрастанию значений красоты. С сортировкой он справится и сам, а найти значения красоты каждой ёлки он попросил вас.
Поскольку красота ёлки может быть очень большой, достаточно найти её значение по модулю 998244353.
Формат входных данных
В первой строке задано число n (2 ≤ n ≤ 1000000) - число городов.
Во второй строке через пробел заданы n чисел a1, a2, ..., an (1 ≤ ai ≤ 109) - красота украшений, используемых в каждом из городов.
В третьей строке задано число k (1 ≤ k ≤ 1000000) - число ёлок.
В i-й из последующих k строк содержатся два числа l и r (1 ≤ l < r ≤ n) - номера первого и последнего городов, которые украшают ёлку с номером i. Гарантируется, что этот диапазон чётной длины, то есть (r - l + 1) делится на 2.
Формат результата
Необходимо вывести k строк, i-я из которых содержит суммарную красоту украшений на i-й ёлке по модулю 998244353.
Примеры
Входные данные 6 1 2 3 4 5 6 3 1 6 1 4 2 5 Результат работы 70 20 28 Входные данные 6 3 1 2 2 1 2 2 2 5 1 4 Результат работы 14 14 Примечания
Система оценки:
Решения, верно работающие при n, k ≤ 40, будут получать не менее 20% . Решения, верно работающие при n, k ≤ 5000, будут получать не менее 50% . Можете решить это задание и отдельно написать на каком языке программирования вы это решали, буду очень блогадарен
Язык не задан, поэтому я напишу только алгоритм. 1) Вводим массив A(10, 10) 2) Открываем пустой массив из одной строки B(10) 3) flag = 0 4) Цикл по i от 1 до 9 4.1) Цикл по k от 1 до 10 (по столбцам) 4.1.1) Копируем i-ую строку из массива А в массив В 4.2) Конец цикла по k 4.3) Цикл по j от i + 1 до 10 (по строкам) 4.3.1) Цикл по k от 1 до 10 (по столбцам) 4.3.1.1) Сравниваем j-ую строку массива А и массив В 4.3.2) Конец цикла по k 4.3.3) Если строки равны, то выводим их на экран. 4.4) Конец цикла по j 5) Конец цикла по i 6) Конец Коротко говоря, алгоритм такой. Сравниваем 1 строку со всеми от 2 до 10. Если строки совпали - выводим их на экран. Можно вывести только номера, можно сами строки. Переходим ко 2 строке. Ее сравниваем от 3 до 10. И так далее. Последнюю 9 строку сравниваем только с 10.
class Main {
public static void main(String[] args){
int[] a = new int[new java.util.Random().nextInt(100)];
for (int i = 0; i < a.length; i++)
a[i] = new java.util.Random().nextInt(499)+1;
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
int b = 0;
int c = 1;
for (int i = 0; i < a.length; i++)
if (a[i] % 3 == 0 && a[i] % 2 == 1) {
b += a[i];
c *= a[i];
}
System.out.print("\nsum: " + b + "\nmulti: " + c);
}
}
Проверка:
$ javac Main.java
327 206 226 438 363 169 433 338 75 127 429 77 271 487 384 173 325 169 250 128 432 214 297 31 238 294 307 151 425 1 19 373 136 246 86 368 183 38 92 186 334 64 486 107 285 240 445 480 271 174 8 325 476 143 169 496 254 437 330 227 496 134 460 20 395 387
sum: 2346
multi: 936904523
1) Вводим массив A(10, 10)
2) Открываем пустой массив из одной строки B(10)
3) flag = 0
4) Цикл по i от 1 до 9
4.1) Цикл по k от 1 до 10 (по столбцам)
4.1.1) Копируем i-ую строку из массива А в массив В
4.2) Конец цикла по k
4.3) Цикл по j от i + 1 до 10 (по строкам)
4.3.1) Цикл по k от 1 до 10 (по столбцам)
4.3.1.1) Сравниваем j-ую строку массива А и массив В
4.3.2) Конец цикла по k
4.3.3) Если строки равны, то выводим их на экран.
4.4) Конец цикла по j
5) Конец цикла по i
6) Конец
Коротко говоря, алгоритм такой.
Сравниваем 1 строку со всеми от 2 до 10. Если строки совпали - выводим их на экран. Можно вывести только номера, можно сами строки.
Переходим ко 2 строке. Ее сравниваем от 3 до 10. И так далее.
Последнюю 9 строку сравниваем только с 10.