Codeforces Round 773 (Div. 1) |
---|
Закончено |
Будучи школьником Стас очень грустил, когда рассадка в школьном автобусе не позволяла ему сесть рядом с другом, поэтому сейчас он вырос и начал писать программу, решающую эту проблему, и ему потребовалось решить такую задачу.
Дан массив $$$a$$$ длины $$$n$$$. Также даны $$$m$$$ различных позиций $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \leq n$$$).
Затем равновероятно выбирается непустое подмножество этих позиций $$$T$$$ и вычисляется $$$$$$\sum_{i=1}^{n} (a_i \cdot \min_{j \in T} \left|i - j\right|).$$$$$$ Иными словами, для каждого индекса массива перемножаются $$$a_i$$$ и расстояние до ближайшей выбранной в подмножество позиции, и эти величины суммируются.
Найдите математическое ожидание этой величины.
Это число нужно найти по модулю $$$998\,244\,353$$$. Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ целые числа и $$$q \neq 0$$$ (mod $$$M$$$). Выведите целое число, равное $$$p \cdot q^{-1}$$$ (mod $$$M$$$). Другими словами, выведите такое целое число $$$x$$$, что $$$0 \leq x < M$$$ и $$$x \cdot q = p$$$ (mod $$$M$$$).
В первой строке находится два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \leq n \leq 10^5$$$).
Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 998\,244\,353$$$).
В третьей строке строке находятся $$$m$$$ различных целых чисел $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \le n$$$).
Для всех $$$1 \leq i < m$$$ гарантируется, что $$$p_i < p_{i+1}$$$.
Выведите единственное целое число — ответ на задачу.
4 2 1 2 3 4 1 4
665496247
6 6 4 2 4 2 4 2 1 2 3 4 5 6
855638030
В первом примере:
Ответ на задачу $$$\frac{20 + 10 + 5}{3} = \frac{35}{3} = 665\,496\,247$$$ (по модулю $$$998\,244\,353$$$).
Название |
---|