/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
正整数 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
頂点に 1 から N までの番号がついた頂点数 N の重み付き無向グラフ G があります。G について 1\leq i\lt j\leq N を満たす任意の整数の組 (i,j) に対して以下が成り立ちます。
- j-i\leq K ならば頂点 i と頂点 j の間に辺が存在して、その辺の重みは \max(A_{P_{i}},A_{P_{j}})
- j-i\gt K ならば頂点 i と頂点 j の間に辺は存在しない
G の最小全域木の辺の重みの和を求めてください。
全ての (1,2,\dots ,N) の順列 P=(P_{1},P_{2},\dots ,P_{N}) に対する f(P) の総和を 998244353 で割ったあまりを求めてください。
制約
- 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) としたとき、
頂点 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 になるので、これを出力します。
入力例 2
2 1 167 924
出力例 2
1848
入力例 3
12 9 22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740
出力例 3
660459584
Score : 700 points
Problem Statement
You are given positive integers N and K, and a sequence of N positive integers: A=(A_{1},A_{2},\dots,A_{N}).
For a permutation P=(P_{1},P_{2},\dots,P_{N}) of (1,2,\dots,N), consider the following problem "MST on Line," and let f(P) the answer.
Problem: MST on Line
We have a weighted undirected graph G with N vertices numbered 1 to N. For every integer pair (i,j) such that 1\leq i\lt j\leq N, the following holds for G.
- If j-i\leq K, there is an edge between vertex i and vertex j, whose weight is \max(A_{P_{i}},A_{P_{j}}).
- If j-i\gt K, there is no edge between vertex i and vertex j.
Find the total weight of the edges of a minimum spanning tree of G.
Find the sum, modulo 998244353, of f(P) over all permutations P=(P_{1},P_{2},\dots ,P_{N}) of (1,2,\dots,N).
Constraints
- 1\leq K\lt N\leq 5000
- 1\leq A_{i}\leq 10^{9}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
A_{1} A_{2} \cdots A_{N}
Output
Print the answer.
Sample Input 1
5 2 3 4 5 2 1
Sample Output 1
1740
For P=(1,2,3,4,5), the following edges form a spanning tree of G:
the edge between vertices 1 and 2 of weight 4,
the edge between vertices 2 and 3 of weight 5,
the edge between vertices 2 and 4 of weight 4, and
the edge between vertices 4 and 5 of weight 2,
for a total weight of 15.
It is impossible to take a spanning tree with a smaller total edge weight, so f(P)=15.
In this way, it can be seen that the sum of f(P) over all permutations P of (1,2,3,4,5) is 1740, which should be printed.
Sample Input 2
2 1 167 924
Sample Output 2
1848
Sample Input 3
12 9 22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740
Sample Output 3
660459584