AT_arc167_c.[ARC167C] MST on Line++

给定正整数 $N,K$ 以及一个长度为 $N$ 的正整数序列 $A=(A_{1},A_{2},\dots,A_{N})$。

对于 $ (1,2,\dots,N) $ 的一个排列 $P=(P_{1},P_{2},\dots,P_{N})$，我们考虑如下的“问题 MST on Line”，并将其答案记为 $f(P)$。

问题 MST on Line

有一个无向带权图 $G$，包含 $N$ 个顶点，顶点编号为 $1$ 到 $N$。对于任意满足 $1\leq i<j\leq N$ 的整数对 $(i,j)$，有如下规则：

• 如果 $j-i\leq K$，则在顶点 $i$ 和顶点 $j$ 之间存在一条边，该边的权值为 $\max(A_{P_{i}},A_{P_{j}})$。
• 如果 $j-i>K$，则顶点 $i$ 和顶点 $j$ 之间没有边。

请计算图 $G$ 的最小生成树的所有边权之和。

请你求出所有 $ (1,2,\dots,N) $ 的排列 $P=(P_{1},P_{2},\dots,P_{N})$ 对应的 $f(P)$ 之和，并对 $998244353$ 取模后输出。

输入通过标准输入给出，格式如下：

$N$ $K$ $A_{1}$ $A_{2}$ $\cdots$ $A_{N}$

请输出答案。

限制条件

• $1\leq K<N\leq 5000$
• $1\leq A_{i}\leq 10^{9}$
• 输入均为整数

样例解释 1

当 $P=(1,2,3,4,5)$ 时，存在如下边：顶点 $1$ 和 $2$ 之间的权值为 $4$ 的边，顶点 $2$ 和 $3$ 之间的权值为 $5$ 的边，顶点 $2$ 和 $4$ 之间的权值为 $4$ 的边，顶点 $4$ 和 $5$ 之间的权值为 $2$ 的边，这 $4$ 条边构成了 $G$ 的一棵生成树，边权之和为 $15$。无法再选取边权和更小的生成树，因此 $f(P)=15$。将所有 $ (1,2,3,4,5) $ 的排列 $P$ 的 $f(P)$ 求和后，结果为 $1740$，请输出该值。

由 ChatGPT 4.1 翻译