#PQJ473x433. QOJ 473_433
QOJ 473_433
2 抽卡 2.1 题目描述 Bob 喜欢抽卡。 Bob 最近入坑了一款叫“主公连结” 的抽卡游戏。游戏中共有n 个不同的角色,编号为 1 ∼n。当Bob 获得其中的编号连续的k 张卡时,就可以组出理论最强阵容。 当期卡池中共有m 张不同的卡,每次抽卡,Bob 都可以等概率随机获得一张卡池中的卡。 如果Bob 抽到了一张他已经拥有的卡,那么什么事都不会发生,等于Bob 浪费了这次抽卡机 会。Bob 是个谨慎的人,他想知道,如果他不停地抽卡直到抽到编号连续的k 张卡时停止抽卡, 期望需要抽多少轮。 2.2 输入格式 第一行输入两个整数m, k。 第二行输入m 个两两不同的整数a1, a2, · · · , am,表示卡池中有哪些角色。 题面中的n 即为最大的ai 的值。 2.3 输出格式 输出一行一个整数,代表期望轮数对p = 998244353 取模后的结果。即,如果期望轮数的 最简分数表示为a b,你需要输出一个整数c 满足c × b ≡a (mod p) 2.4 样例输入1 3 2 1 2 3 2.5 样例输出1 499122180 2.6 样例解释1 如果第一轮抽到的是2 号卡,那么期望需要抽1 + 3 2 轮;如果第一轮抽到的是1 号卡或3 号卡,那么期望需要抽1 + 3 轮。故答案为1 3(1 + 3 2) + 2 3(1 + 3) = 3.5 2.7 样例输入2 10 2 6
1 2 3 4 5 7 8 9 11 12 2.8 样例输出2 839792873 2.9 数据范围与约定 对于前10% 的数据,m ≤10。 对于另外10% 的数据,m ≤500 且k = m −1。 对于另外10% 的数据,m ≤500 且保证有且仅有一组理论最强阵容。 对于另外10% 的数据,m ≤500 且保证任意两组可抽出的理论最强阵容不交。 对于前50% 的数据,m ≤500。 对于前70% 的数据,m ≤5000。 对于另外10% 的数据,k = 5。 对于另外10% 的数据,k = 2000。 对于100% 的数据,1 ≤m ≤200000, 1 ≤ai ≤2m, 2 ≤k ≤m,保证卡池中至少存在一组 可抽出的理论最强阵容(即编号连续的k 张卡)。 7