Codeforces Round 773 (Div. 1) |
---|
Finished |
You are given an array $$$a$$$ of length $$$n$$$. Also you are given $$$m$$$ distinct positions $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \leq n$$$).
A non-empty subset of these positions $$$T$$$ is randomly selected with equal probability and the following value is calculated: $$$$$$\sum_{i=1}^{n} (a_i \cdot \min_{j \in T} \left|i - j\right|).$$$$$$ In other word, for each index of the array, $$$a_i$$$ and the distance to the closest chosen position are multiplied, and then these values are summed up.
Find the expected value of this sum.
This value must be found modulo $$$998\,244\,353$$$. More formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be represented as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \neq 0$$$ (mod $$$M$$$). Output the integer equal to $$$p \cdot q^{-1}$$$ (mod $$$M$$$). In other words, output such integer $$$x$$$ that $$$0 \leq x < M$$$ and $$$x \cdot q = p$$$ (mod $$$M$$$).
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 998\,244\,353$$$).
The third line contains $$$m$$$ distinct integers $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \le n$$$).
For every $$$1 \leq i < m$$$ it is guaranteed that $$$p_i < p_{i+1}$$$.
Print a single integer — the answer to the problem.
4 2 1 2 3 4 1 4
665496247
6 6 4 2 4 2 4 2 1 2 3 4 5 6
855638030
In the first test:
The answer to the problem is $$$\frac{20 + 10 + 5}{3} = \frac{35}{3} = 665\,496\,247$$$ (modulo $$$998\,244\,353$$$).
Name |
---|