← 返回题目列表

AtCoder · arc167_c

C. MST 上线++

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

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