Special Positions
Contest: Codeforces Round 773 (Div. 1)
Difficulty rating: 3300
Tags: combinatorics, divide and conquer, fft, math

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$$$).

Input format:
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}$$$.

Output format:
Print a single integer — the answer to the problem.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
In the first test:

- If only $$$1$$$ is choosen, than the value equals to $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 3 = 20$$$.
- If only $$$4$$$ is choosen, than the value equals to $$$1 \cdot 3 + 2 \cdot 2 + 3 \cdot 1 + 4 \cdot 0 = 10$$$.
- If both positions are chosen, than the value equals to $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 = 5$$$.

The answer to the problem is $$$\frac{20 + 10 + 5}{3} = \frac{35}{3} = 665\,496\,247$$$ (modulo $$$998\,244\,353$$$).

Example input:
4 2
1 2 3 4
1 4

Example output:
665496247

Example input:
6 6
4 2 4 2 4 2
1 2 3 4 5 6

Example output:
855638030

Editorial:
First of all, calculate for each index the total sum of distances among all subsets if the closest selected position is to the left. Let $$$suf_i = 2^{cnt_i}$$$, where $$$cnt_i$$$ — the number of cpecial positions at $$$i$$$ or to the right of $$$i$$$ (if $$$i > n$$$ then $$$cnt_i = 0$$$).
Let $$$special_i = 1$$$ if position $$$i$$$ is special, otherwise $$$special_i = 0$$$.
It's not hard to see, that the value for the position $$$pos$$$ in this case equals to $$$\sum_{i = 1}^{pos-1} \sum_{j + i = 2 * pos} special_i \cdot suf_i \cdot (pos - i)$$$.
Then for each $$$pos$$$ calculate two values:
1. $$$\sum_{i = 1}^{pos-1} \sum_{j + i = 2 * pos} special_i \cdot suf_i \cdot i$$$
2. $$$\sum_{i = 1}^{pos-1} \sum_{j + i = 2 * pos} special_i \cdot suf_i$$$
Since $$$j > i$$$ we can find first value using DNC (the second value we will find similary): we want to consider every $$$l \le i < j \le r$$$. Then halve this segment: $$$m = \frac{l + r}{2}$$$. Then create two polynomials:
1. The polynomial $$$P$$$ of size $$$m - l + 1$$$, where $$$P_i = special_{l + i} \cdot (l + r)$$$.
2. The polynomial $$$Q$$$ of size $$$r - m$$$, where $$$Q_i = suf_{m + 1 + i}$$$.
By multiplying this two polinomials we can recalculate the values for positions from $$$l + m + 1$$$ to $$$m + r$$$ and then solve two parts recursively.
Thus we can find for each index the total sum of distances among all subsets if the closest selected position is to the left. To find for each index the total sum of distances among all subsets if the closest selected positions is to the right we can do the same stuff but in inverse order.
Note, that we need to consider the case where the closest selected position to the left and the closest selected position are at the same distance from $$$pos$$$. It can be done by changing $$$cnt_i$$$ in one of the cases by the number of special positinos strickly to the right of $$$i$$$.
It can be implemented in $$$O(n \log^2{n})$$$ using FFT.