#3315. 「ZJOI2020」抽卡

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

Bob 喜欢抽卡。

Bob 最近入坑了一款叫“主公连结” 的抽卡游戏。游戏中共有 n 个不同的角色,编号为 1\sim n 。当 Bob 获得其中的编号连续的 k 张卡时,就可以组出理论最强阵容。

当期卡池中共有 m 张不同的卡,每次抽卡,Bob 都可以等概率随机获得一张卡池中的卡。如果 Bob 抽到了一张他已经拥有的卡,那么什么事都不会发生,等于 Bob 浪费了这次抽卡机会。Bob 是个谨慎的人,他想知道,如果他不停地抽卡直到抽到编号连续的 k 张卡时停止抽卡,期望需要抽多少轮。

输入格式

第一行输入两个整数 m, k

第二行输入 m 个两两不同的整数 a_1, a_2, \dots, a_m ,表示卡池中有哪些角色。

题面中的 n 即为最大的 a_i 的值。

输出格式

输出一行一个整数,代表期望轮数对 p = 998244353 取模后的结果。即,如果期望数量的最简分数表示为 \frac ab ,你需要输出一个整数 c 满足 c\times b \equiv a \pmod p

样例

样例输入 1

3 2
1 2 3

样例输出 1

499122180

样例解释 1

如果第一轮抽到的是 2 号卡,那么期望需要抽 1 + \frac 32 轮;如果第一轮抽到的是 1 号卡或 3 号卡,那么期望需要抽 1 + 3 轮。故答案为 \frac 13(1 + \frac 32) + \frac 23(1 + 3) = 3.5

样例输入 2

10 2
1 2 3 4 5 7 8 9 11 12

样例输出 2

839792873

数据范围与提示

对于前 10\% 的数据, m\le 10

对于另外 10\% 的数据, m \le 500 k = m − 1

对于另外 10\% 的数据, m \le 500 且保证有且仅有一组理论最强阵容。

对于另外 10\% 的数据, m \le 500 且保证任意两组可抽出的理论最强阵容不交。

对于前 50\% 的数据, m \le 500

对于前 70\% 的数据, m \le 5000

对于另外 10\% 的数据, k = 5

对于另外 10\% 的数据, k = 2000

对于 100\% 的数据, 1 \le m \le 200000, 1 \le a_i \le 2m, 2 \le k \le m ,保证卡池中至少存在一组可抽出的理论最强阵容(即编号连续的 k 张卡)。