No.2635 MST on Line++ 2
ebi_fly
noya2Problem Statement
You are given positive integers $N,K$ and a sequence of positive integers $A=(A_{1},A_{2},\dots,A_{N})$ of length $N$.
For a permutation $P=(P_{1},P_{2},\dots ,P_{N})$ of $(1,2,\dots ,N)$, consider the following "Problem MST on Line 2", and let $f(P)$ denote its answer.
Problem MST on Line 2
There is a weighted undirected graph $G$ with $N$ vertices numbered from $1$ to $N$. For every pair of integers $(i,j)$ satisfying $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$, and its weight is $\min(A_{P_{i}},A_{P_{j}})$
- If $j-i\gt K$, there is no edge between vertex $i$ and vertex $j$
Find the sum of the edge weights of a minimum spanning tree of $G$.
Find the sum of $f(P)$ over all permutations $P=(P_{1},P_{2},\dots ,P_{N})$ of $(1,2,\dots ,N)$, modulo $998244353$.
Constraints
- $1\leq K\lt N\leq$ $2\times 10^{5}$
- $1\leq A_{i}\leq 10^{9}$
- All input values are integers
Input
$N$ $K$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
Output
Output the answer.
Sample
Sample 1
Input
5 2 3 4 5 2 1
Output
648
Sample 2
Input
2 1 924 167
Output
334
Sample 3
Input
12 9 22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740
Output
475260609
Sample 4
Input
17 3 20508 7568 87729 35274 46341 50587 23669 42805 25381 3806 28055 80697 94519 33016 90880 370 81146
Output
92588775
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。