← 返回题目列表

Codeforces · 1641/E

E. 特殊职位

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$。此外,您还会获得 $$$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}$$$。

输出

打印一个整数——问题的答案。

示例

输入 #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

注意

在第一个测试中:

- 如果仅选择 $$$1$$$,则该值等于 $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 3 = 20$$$。
- 如果仅选择 $$$4$$$,则该值等于 $$$1 \cdot 3 + 2 \cdot 2 + 3 \cdot 1 + 4 \cdot 0 = 10$$$。
- 如果选择了两个位置,则该值等于 $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 = 5$$$。

问题的答案是 $$$\frac{20 + 10 + 5}{3} = \frac{35}{3} = 665\,496\,247$$$ (模 $$$998\,244\,353$$$)。