← 返回题目列表

AtCoder · arc120_f

F. 酒贼

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

分数: 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