Special Positions

题意翻译

给定长度为 $n$ 的数组 $a$，长度为 $m$ 的数组 $p$，其中 $1 \le p_i \le n$ ，而且 $\forall j, p_i \not = p_j$。 在 $p$ 中等概率选定一个非空集合，求 $\sum_{i = 1} ^ n a_i \times |i - p_j|$ 其中 $p_j$ 是选定集合中 $|i - p_j|$ 最小的 $p$。 $m \le n \le 10^5, a_i \le 998244352, 1 \le p_i \le n, p_i$ 两两不同。

题目描述

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.</p><p>Find the expected value of this sum.</p><p>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 &lt; 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.

输入输出样例

输入样例 #1

4 2
1 2 3 4
1 4

输出样例 #1

665496247

输入样例 #2

6 6
4 2 4 2 4 2
1 2 3 4 5 6

输出样例 #2

855638030

说明

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