Question

Ёлка для енота В стране енотов есть 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.

Answer 1

Ответ:

#include <bits/stdc++.h>

using namespace std;

int main(){

       ios_base::sync_with_stdio(0);

       cin.tie(0);cout.tie(0);

       int N,k;

       int a[1000000];

       map <pair <int, int>, int> mem;

       cin >> N;

       //b.reserve(N);

       memset(a,0,sizeof a);

       //memset(b,0,b.size()*sizeof int);

       for (int i=0;i<N;i++)

               cin >> a[i];

       cin >> k;

       for (int i=0;i<k;i++){

       int tmp,tmp2,tmp3,tmp4,sum{0};

       cin >> tmp >> tmp2;

       tmp--;tmp2--;

       if (mem.find({tmp,tmp2})!=mem.end()) {cout<< mem[ {tmp,tmp2} ] << endl; continue;}

       tmp3=tmp;

       tmp4=tmp2;

       for(int x=0;x<(tmp4-tmp3)/2+1;x++){

       for(int z=0;z<(tmp2-tmp)/2+1;z++){

       if (mem.find({tmp,tmp2})!=mem.end()) {sum= (sum+mem[ {tmp,tmp2} ])%998244353; break;}

       for(int j=tmp+z;j<=tmp2-z;j++){

       sum=(sum+a[j])%998244353;

       }}

       tmp++;tmp2--;

       }

       cout << sum << endl;

       mem[{tmp3,tmp4}]=sum;

       }

       return 0;

}

Объяснение:

Answer 2

Для решения этой задачи можно воспользоваться алгоритмом динамического программирования. Давайте сначала преобразуем входные данные для удобства. Создадим массив prefix_sum, где prefix_sum[i] будет хранить сумму красоты украшений в первых i городах. Также создадим массив dp, где dp[i] будет хранить суммарную красоту украшений для ёлки с номером i.

Затем, для каждой ёлки с номером i, мы можем найти суммарную красоту украшений следующим образом:

1. Вычисляем разницу между prefix_sum[r] и prefix_sum[l-1] (если l=1, то используем просто prefix_sum[r]), чтобы получить сумму красоты украшений в городах с номерами от l до r.

2. Создаем переменную beauty, которая будет хранить суммарную красоту ёлки.

3. Далее, для каждого j от 1 до (r-l)/2 (половина от длины диапазона), мы будем добавлять к beauty значение dp[j] * разница (prefix_sum[r-j] - prefix_sum[l-1+j]).

4. Записываем beauty в dp[i].

5. В конце, выводим dp[i] по модулю 998244353.

Пример кода на Python:

pythonCopy code
MOD = 998244353

n = int(input())
beauty_values = list(map(int, input().split()))
k = int(input())

prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
    prefix_sum[i] = prefix_sum[i - 1] + beauty_values[i - 1]

dp = [0] * (k + 1)

for i in range(1, k + 1):
    l, r = map(int, input().split())
    diff = prefix_sum[r] - prefix_sum[l - 1]
    beauty = diff
    for j in range(1, (r - l) // 2 + 1):
        beauty += dp[j] * (prefix_sum[r - j] - prefix_sum[l - 1 + j])
    dp[i] = beauty % MOD
    print(dp[i])

Этот код вычисляет суммарную красоту украшений для каждой ёлки и выводит её по модулю 998244353.