#PQJ301x4472. QOJ 301_4472

    ID: 2887 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2019组合数学概率期望

QOJ 301_4472

第一试珍珠(pearl) IOI 2019 中国国家队选拔 珍珠(pearl) 【题目背景】 白云苍狗,沧海桑田。 白云的眼前只剩下了模糊的一片。 在若隐若现之中,它看到了一个个小小的珍珠,有一些发着五彩的光芒。这些珍珠 是白兔留下来的,每颗珍珠有一个颜色,为D 种颜色中随机的一种。 白云想把这些珍珠放进一些小瓶子中,每个瓶子能恰好容纳两颗珍珠。不过它也有 要求,每个瓶子必须装满,并且装的都是相同颜色的珍珠。 白云希望能得到至少m 个装满珍珠的瓶子,它想知道它的愿望能被实现的概率是 多少呢? 【题目描述】 有n 个在范围[1, D] 内的整数均匀随机变量。 求至少能选出m 个瓶子,使得存在一种方案,选择一些变量,并把选出来的每一 个变量放到一个瓶子中,满足每个瓶子都恰好装两个值相同的变量的概率。 请输出概率乘上Dn 后对998244353 取模的值。取模部分说明可参考第一题。 【输入格式】 从文件pearl.in 中读入数据。 输入仅一行,三个用空格隔开的整数D, n, m 【输出格式】 输出到文件pearl.out 中。 输出一个整数,表示所求概率乘上Dn 后对998244353 取模的结果。 【样例1 输入】 2 2 1 【样例1 输出】 2 第4 页 共9 页 第一试珍珠(pearl) IOI 2019 中国国家队选拔 【样例1 解释】 情况1 : 第一个变量为1,第二个变量为1 情况2 : 第一个变量为1,第二个变量为2 情况3 : 第一个变量为2,第二个变量为1 情况4 : 第一个变量为2,第二个变量为2 其中情况1 和4 可以把两个变量放到一个瓶子中 情况2 和3 中两个变量的值不相同,所以不能放到同一个瓶子中 【样例2】 见选手目录下的pearl/pearl2.in 与pearl/pearl2.ans。 【样例3】 见选手目录下的pearl/pearl3.in 与pearl/pearl3.ans。 第5 页 共9 页 第一试珍珠(pearl) IOI 2019 中国国家队选拔 【测试数据约定】 测试点编号 D n m ≤10 1 ≤2 ≤20 2 3 4 ≤100 ≤100 5 6 7 ≤n 8 9 ≤4000 ≤4000 10 11 12 13 ≤300 14 15 ≤0 16 ≤1 17 ≤2 18 ≤1000000000 19 20 ≤100000 21 ≤n 22 23 24 25 所有测试点均满足1 ≤m ≤n ≤109￿1 ≤D ≤105 第6 页 共9 页