A5918 | 「ZJOI2020」抽卡
时间限制5s
内存限制512MB
通过 / 提交0/0
题目描述
Bob 喜欢抽卡。
Bob 最近入坑了一款叫“主公连结” 的抽卡游戏。游戏中共有 $n$ 个不同的角色，编号为 $1\sim n$。当 Bob 获得其中的编号连续的 $k$ 张卡时，就可以组出理论最强阵容。
当期卡池中共有 $m$ 张不同的卡，每次抽卡，Bob 都可以等概率随机获得一张卡池中的卡。如果 Bob 抽到了一张他已经拥有的卡，那么什么事都不会发生，等于 Bob 浪费了这次抽卡机会。Bob 是个谨慎的人，他想知道，如果他不停地抽卡直到抽到编号连续的 $k$ 张卡时停止抽卡，期望需要抽多少轮。
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$ 的值。
第二行输入 $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
输入 #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$ 张卡）。
对于另外 $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$ 张卡）。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？