UOJ Logo Universal Online Judge

UOJ

#311. 【UNR #2】积劳成疾

统计

琪琪gaygay的假老师与gay里gay气的稳爷爷相依为gay,但自从假老师接了UOJ管理员的锅,造题的任务便一个接着一个,由于UOJ审题工作十分繁重,假老师常常累的意识模糊,这让稳爷爷十分担心。

经过长期的观察,稳爷爷发现假老师每天会恰好审 $k$ 道题。假设现在UOJ有 $n$ 道题要审(编号为 $1, \dots, n$),为了让审题工作更加细致,假老师会选择这样一种方式审题:

  • 第一天审编号为 $1, \dots, k$ 的题,
  • 第二天审编号为 $2, \dots, k+1$ 的题,
  • ……
  • 第 $n-k+1$ 审编号为 $n-k+1, \dots, n$ 的题。

稳爷爷接着还发现,假老师每天审题的劳累度跟当天审的 $k$ 道题中最难的题有关。每道题都有一个难度系数,是一个介于 $1$ 到 $n$ 之间的整数。假老师对于不同难度的题有不同的劳累度,可用一组常数 $w_1, \dots, w_n$ 表示。若假老师某一天审的题中难度系数的最大值为 $d$,则假老师这一天的劳累度为 $w_d$(由于假老师对题目难度有独特的口味,$w_d$ 并不一定是单调递减的)

假老师 $n-k+1$ 天的审题工作总劳累度定义为每一天劳累度的乘积

然而作为UOJ工作人员,假老师自然不能透露任何难度信息,所以稳爷爷只好认为每道题的难度在 $1, \dots, n$ 中均匀随机,而他想知道的就是假老师总劳累度的期望值。

显然这个期望值 $E$ 乘以 $n^n$ 一定是一个整数,所以你只需要输出 $n^n E$ 对 $998244353$ 取模的结果即可。

输入格式

第一行两个正整数 $n,k$ 意义如题目所述。

第二行 $n$ 个整数表示 $w_1, \dots, w_n$。

输出格式

输出一行一个整数,表示 $n^n E$ 对 $998244353$ 取模的结果。

样例一

input

2 2
1 2

output

7

explanation

共有 $\{1,1\},\{1,2\}, \{2,1\}, \{2,2\}$ 四种难度组合,劳累度期望为为 $\frac{7}{4}$。

样例二

input

5 3
2 4 1 3 5

output

190493

样例三

见样例数据下载。

限制与约定

本题采用捆绑评测,对于一个子任务,只有通过其中所有的数据才可以获得分数。

对于全部数据,$1 \leq k \leq n \leq 400, 0 \leq w_i < 998244353$。

各个测试点限制见下表:

子任务 分值 限制
120$n \leq 8$
215$n \leq 15$
320$n \leq 300, k \leq 2$
415$n \leq 300, k \leq 3$
530$n \leq 400$

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载