分数: 800 点
问题陈述
问题 F 和 F2 具有相同的问题陈述,但具有不同的约束和时间限制。
有 N 高桥的地窖里的酒瓶,从左到右排列成一排。
的美味 i左边第一个瓶子是 A_i.
青木会选择 K 这些瓶子 N 并偷走它们。然而,如果满足以下条件,高桥足够细心,就会注意到盗窃:
- 存在 D 连续瓶子,其中两个或更多瓶子被盗。 (D = 2 在这个问题中。)
对于每种在不被高桥注意到的情况下偷瓶子的方法,找到被盗瓶子的总味道,然后找到所有这些值的总和。
由于总和可能很大,因此将其模数打印出来 998244353.
约束
- D = 2
- 2 \le N \le 3 \times 10^5
- 1 \le K \le \left\lceil \frac{N}{D} \right\rceil (\left\lceil x \right\rceil 表示不小于的最小整数 x.)
- 1 \le A_i \lt 998244353
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K D A_1 A_2 A_3 \dots A_N
输出
打印模数之和 998244353.
示例输入 1
4 2 2 1 4 2 3
示例输出 1
14
偷瓶子的可能方法以及每种方法的总味道如下:
- 偷 1-st 和 3- 从左起第 3 瓶,为总的美味 1 + 2 = 3.
- 偷 1-st 和 4从左起第 3 瓶,为总的美味 1 + 3 = 4.
- 偷 2-nd 和 4从左起第 3 瓶,为总的美味 4 + 3 = 7.
因此,答案是 3 + 4 + 7 = 14.
示例输入 2
5 3 2 4 7 5 3 8
示例输出 2
17
别无选择,只能偷 1-st, 3-rd,和 5第瓶。
示例输入 3
12 4 2 107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094
示例输出 3
136993014