AT_arc120_f [ARC120F] Wine Thief

[problemUrl]: https://atcoder.jp/contests/arc120/tasks/arc120_f **问题 F 和问题 F2 是相同的问题，但约束条件和运行时间限制不同。** 高桥君的仓库里有 $N$ 瓶葡萄酒，按左右方向排成一行。从左起第 $i$ 瓶葡萄酒的美味度为 $A_i$。 青木君现在要从这 $N$ 瓶葡萄酒中，恰好选出 $K$ 瓶来偷走。但是，高桥君非常警觉，如果满足以下条件，他就会发现葡萄酒被偷了： - 存在某一段连续的 $D$ 瓶葡萄酒，其中被偷走的有 $2$ 瓶或以上（本题中 $D=2$）。 请计算在不被高桥君发现的所有偷盗方式中，偷走的葡萄酒美味度之和的总和。 由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入以如下格式从标准输入给出： > $N$ $K$ $D$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

请输出答案对 $998244353$ 取模的结果。

## 约束条件 - $D=2$ - $2 \leq N \leq 3 \times 10^5$ - $1 \leq K \leq \left\lceil \frac{N}{D} \right\rceil$（$\left\lceil x \right\rceil$ 表示大于等于 $x$ 的最小整数） - $1 \leq A_i < 998244353$ - 输入中的所有数值均为整数 ## 样例解释 1 偷盗方式及偷走葡萄酒美味度之和如下： - 偷第 $1$ 瓶和第 $3$ 瓶：美味度之和为 $1+2=3$ - 偷第 $1$ 瓶和第 $4$ 瓶：美味度之和为 $1+3=4$ - 偷第 $2$ 瓶和第 $4$ 瓶：美味度之和为 $4+3=7$ 因此答案为 $3+4+7=14$。 ## 样例解释 2 只能偷第 $1,3,5$ 瓶葡萄酒。 由 ChatGPT 4.1 翻译