← 返回题目列表

AtCoder · waipc_qual_g

G. K 段总和的最大值总和

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

配点 : 1200 点

問題文

长度 小于或等于 N 整数序列 给出 A=(A_1,A_2,\ldots,A_N) 以及整数 K 被给出。 函数 f(L,R) (1 \leq L \leq R \leq N) 定义如下。

  • R-L +1 < K 时,f(L,R)=0 。
  • 否则,(A_L,A_{L+1},\ldots,A_{R}) 减去 K 考虑以不重叠的方式取出个非空连续子序列。 "最左边子序列中包含元素的总和的绝对值"+"其他子序列中包含元素的总和"可能达到的最大值 f(L,R) 为。 更形式地说,f(L,R)=\max_{L\leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_K \leq r_K \leq R}(|\sum_{l_1 \leq i \leq r_1} A_i| + \sum_{2 \leq j \leq K} \sum_{l_j \leq i \leq r_j} A_i) 。

\sum_{1 \leq L \leq R \leq N} f(L,R) 该值应乘以 998244353 求除以 的余数 (将负数求余数也 0 以上 998244353 在以下范围内求得)。

制約

  • 1 \leq K \leq N \leq 250000
  • K \leq 4
  • -10^9 \leq A_i \leq 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 \ldots A_N

出力

打印答案。


入力例 1

3 2
2 -2 -1

出力例 1

2

K \leq R-L+1 以同样的方式定义 f(L,R) 的值如下。 满足

  • (L,R)=(1,2) 时: (l_1,r_1,l_2,r_2)=(1,1,2,2) 达到最大值的f(L,R)=0 变为。
  • (L,R)=(1,3) 时: (l_1,r_1,l_2,r_2)=(1,1,3,3) 达到最大值的f(L,R)=1 变为。
  • (L,R)=(2,3) 时: (l_1,r_1,l_2,r_2)=(2,2,3,3) 达到最大值的f(L,R)=1 变为。

因此,即它们的和 2 是答案。


入力例 2

5 2
-1 -2 -4 -8 -16

出力例 2

998244327

入力例 3

10 3
-21 -75 -29 -5 -99 -60 -75 -98 -48 -66

出力例 3

2320

入力例 4

15 4
-296045184 -17176032 -21940358 388585142 -410726492 244506160 -324910496 -99305133 -45869288 -25027474 -109128673 105493294 -6256129 -40956935 -33486703

出力例 4

51969020