{"problem":{"name":"MST on Line++","description":{"content":"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 fo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc167_c"},"statements":[{"statement_type":"Markdown","content":"You are given positive integers $N$ and $K$, and a sequence of $N$ positive integers: $A=(A_{1},A_{2},\\dots,A_{N})$.\nFor 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.\n\n> **Problem: MST on Line**\n> 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$.\n> \n> *   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}})$**.\n> *   If $j-i\\gt K$, there is no edge between vertex $i$ and vertex $j$.\n> \n> Find the total weight of the edges of a minimum spanning tree of $G$.\n\nFind the sum, modulo $998244353$, of $f(P)$ over all permutations $P=(P_{1},P_{2},\\dots ,P_{N})$ of $(1,2,\\dots,N)$.\n\n## Constraints\n\n*   $1\\leq K\\lt N\\leq 5000$\n*   $1\\leq A_{i}\\leq 10^{9}$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_{1}$ $A_{2}$ $\\cdots$ $A_{N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc167_c","tags":[],"sample_group":[["5 2\n3 4 5 2 1","1740\n\nFor $P=(1,2,3,4,5)$, the following edges form a spanning tree of $G$:\nthe edge between vertices $1$ and $2$ of weight $4$,\nthe edge between vertices $2$ and $3$ of weight $5$,\nthe edge between vertices $2$ and $4$ of weight $4$, and\nthe edge between vertices $4$ and $5$ of weight $2$,\nfor a total weight of $15$.\nIt is impossible to take a spanning tree with a smaller total edge weight, so $f(P)=15$.\nIn 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."],["2 1\n167 924","1848"],["12 9\n22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740","660459584"]],"created_at":"2026-03-03 11:01:14"}}