P8107 [Cnoi2021] 未来试题

在 Cnoi2021 验题查重环节中，Cirno 发现在遥远的未来，2077 年蚯蚓科技大学（某不知名外界学校）的新生赛中的一道题竟然意外地与这套试题的某题有着 $9\%$ 的相似度。 >给你一个正整数 $n$，求等概率生成一个长度为 $n$ 的全排列时，全排列中逆序对数量的期望在$\bmod 10^9+7$ 的意义下的答案。（2077-xidian-freshman-online Problem.D） 答案显然是 $\frac{n(n-1)}{4}$。 作为算术天才，Cirno 一眼就看了出来。 但无需担忧，与未来试题相撞不算撞题，所以这道题便出现在了你的面前。

给你两个正整数 $n,k$。 对 $\forall i \in [0,k)$，求等概率生成一个长度为 $n$ 的全排列时，全排列中逆序的个数对 $k$ 取模后，余数为 $i$ 的概率，答案对 $998244353$ 取模。

一行，输入两个整数 $n,k$。

一行，$k$ 个整数，用空格隔开，第 $i$ 个表示全排列中逆序的个数对 $k$ 取模后，余数为 $i-1$ 的概率。

**样例解释** |逆序对数|排列| |-----|-----| |0|$(1,2,3,4)$| |1|$(1,2,4,3)(1,3,2,4)(2,1,3,4)$| |2|$(1,3,4,2)(1,4,2,3)(2,1,4,3)(2,3,1,4)(3,1,2,4)$| |3|$(1,4,3,2)(2,3,4,1)(2,4,1,3)(3,1,4,2)(3,2,1,4)(4,1,2,3)$| |4|$(2,4,3,1)(3,2,4,1)(3,4,1,2)(4,1,3,2)(4,2,1,3)$| |5|$(3,4,2,1)(4,2,3,1)(4,3,1,2)$| |6|$(4,3,2,1)$| **数据范围** 对于 $100\%$ 的数据保证 $1\le n\le 10^5$，$2\le k\le1000$。 重收录自 XDUCPC 2021 现场赛 F。