分数: 700 点
问题陈述
给你正整数 N 和 K,以及一系列 N 正整数: A=(A_{1},A_{2},\dots,A_{N}).
对于排列 P=(P_{1},P_{2},\dots,P_{N}) of (1,2,\dots,N),考虑以下问题“MST on Line”,并让 f(P) 答案。
问题:MST 上线
我们有一个加权无向图 G 与 N 顶点编号 1 to N。对于每个整数对 (i,j) 这样 1\leq i\lt j\leq N,以下内容成立 G.
- If j-i\leq K,顶点之间有一条边 i 和顶点 j,其权重为 \max(A_{P_{i}},A_{P_{j}}).
- If j-i\gt K,顶点之间没有边 i 和顶点 j.
求最小生成树的边的总权重 G.
求总和,模 998244353,属于 f(P) 所有排列 P=(P_{1},P_{2},\dots ,P_{N}) of (1,2,\dots,N).
约束
- 1\leq K\lt N\leq 5000
- 1\leq A_{i}\leq 10^{9}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K
A_{1} A_{2} \cdots A_{N}
输出
打印答案。
示例输入 1
5 2 3 4 5 2 1
示例输出 1
1740
对于 P=(1,2,3,4,5),以下边形成生成树 G:
顶点之间的边 1 和 2 的重量 4,
顶点之间的边 2 和 3 的重量 5,
顶点之间的边 2 和 4 的重量 4,和
顶点之间的边 4 和 5 的重量 2,
总重量为 15.
不可能采取总边权较小的生成树,所以 f(P)=15.
这样可以看出,总和 f(P) 所有排列 P of (1,2,3,4,5) is 1740,应该打印出来。
示例输入 2
2 1 167 924
示例输出 2
1848
示例输入 3
12 9 22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740
示例输出 3
660459584