P4707 重返现世

    • 187通过
    • 602提交
  • 题目提供者 Sdchr
  • 评测方式 云端评测
  • 标签
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    为了打开返回现世的大门,Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 $n$ 种原料,只需要集齐任意 $k$ 种,就可以开始制作。

    Yopilla 来到了迷失大陆的核心地域。每个单位时间,这片地域就会随机生成一种原料。每种原料被生成的概率是不同的,第 $i$ 种原料被生成的概率是 $\frac{p_i}{m}$ 。如果 Yopilla 没有这种原料,那么就可以进行收集。

    Yopilla 急于知道,他收集到任意 $k$ 种原料的期望时间,答案对 $998244353$ 取模。

    输入输出格式

    输入格式:

    第一行三个数 $n, k, m$ 。

    第二行 $n$ 个数 $p_1, p_2, ..., p_n$ 。

    输出格式:

    输出一行。

    输入输出样例

    输入样例#1: 复制
    3 3 3
    1 1 1
    
    输出样例#1: 复制
    499122182
    

    说明

    对于 $10 \%$ 的数据,$p_1 = p_2 = ... = p_m$ 。

    对于另外 $10 \%$ 的数据,$k = n$ 。

    对于 $70 \%$ 的数据,$n \le 100$ 。

    对于 $100 \%$ 的数据,$1 \le n \le 1000$ ,$1 \le k \le n, \lvert n - k \rvert \le 10$ ,$0 \le p_i \le m, \sum p = m, 1 \le m \le 10000$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。