A5868 | 「CTS2019 | CTSC2019」珍珠
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
>白云苍狗，沧海桑田。
白云的眼前只剩下了模糊的一片。
在若隐若现之中，它看到了一个个小小的珍珠，有一些发着五彩的光芒。这些珍珠是白兔留下来的，每颗珍珠有一个颜色，为 $D$ 种颜色中随机的一种。
白云想把这些珍珠放进一些小瓶子中，每个瓶子能恰好容纳两颗珍珠。不过它也有要求，每个瓶子必须装满，并且装的都是相同颜色的珍珠。
白云希望能得到至少 $m$ 个装满珍珠的瓶子，它想知道它的愿望能被实现的概率是多少呢？
有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。
求至少能选出 $m$ 个瓶子，使得存在一种方案，选择一些变量，并把选出来的每一个变量放到一个瓶子中，满足每个瓶子都恰好装两个值相同的变量的概率。
请输出概率乘上 $D^n$ 后对 $998244353$ 取模的值。取模部分说明可参考[第一题（随机立方体）](https://loj.ac/problem/3119)。
白云的眼前只剩下了模糊的一片。
在若隐若现之中，它看到了一个个小小的珍珠，有一些发着五彩的光芒。这些珍珠是白兔留下来的，每颗珍珠有一个颜色，为 $D$ 种颜色中随机的一种。
白云想把这些珍珠放进一些小瓶子中，每个瓶子能恰好容纳两颗珍珠。不过它也有要求，每个瓶子必须装满，并且装的都是相同颜色的珍珠。
白云希望能得到至少 $m$ 个装满珍珠的瓶子，它想知道它的愿望能被实现的概率是多少呢？
有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。
求至少能选出 $m$ 个瓶子，使得存在一种方案，选择一些变量，并把选出来的每一个变量放到一个瓶子中，满足每个瓶子都恰好装两个值相同的变量的概率。
请输出概率乘上 $D^n$ 后对 $998244353$ 取模的值。取模部分说明可参考[第一题（随机立方体）](https://loj.ac/problem/3119)。
输入格式
输入仅一行，三个用空格隔开的整数 $D,n,m$。
输出格式
输出一个整数，表示所求概率乘上 $D^n$ 后对 $998244353$ 取模的结果。
输入输出样例
输入 #1
2 2 1
输出 #1
2
|测试点编号|$D$|$n$|$m$|
|:-:|:-:|:-:|:-:|
|$1$|$\le 2$|$\le 10$|$\le n$|
|$2$|$\le 2$|$\le 20$|$\le n$|
|$3$|$\le 100$|$\le 100$|$\le n$|
|$4$|$\le 100$|$\le 100$|$\le n$|
|$5$|$\le 100$|$\le 100$|$\le n$|
|$6$|$\le 100$|$\le 100$|$\le n$|
|$7$|$\le 100$|$\le 100$|$\le n$|
|$8$|$\le 4000$|$\le 4000$|$\le n$|
|$9$|$\le 4000$|$\le 4000$|$\le n$|
|$10$|$\le 4000$|$\le 4000$|$\le n$|
|$11$|$\le 4000$|$\le 4000$|$\le n$|
|$12$|$\le 4000$|$\le 4000$|$\le n$|
|$13$|$\le 300$|$\le 1000000000$|$\le n$|
|$14$|$\le 300$|$\le 1000000000$|$\le n$|
|$15$|$\le 300$|$\le 1000000000$|$\le n$|
|$16$|$\le 100000$|$\le 1000000000$|$\le 0$|
|$17$|$\le 100000$|$\le 1000000000$|$\le 1$|
|$18$|$\le 100000$|$\le 1000000000$|$\le 2$|
|$19$|$\le 100000$|$\le 1000000000$|$\le n$|
|$20$|$\le 100000$|$\le 1000000000$|$\le n$|
|$21$|$\le 100000$|$\le 1000000000$|$\le n$|
|$22$|$\le 100000$|$\le 1000000000$|$\le n$|
|$23$|$\le 100000$|$\le 1000000000$|$\le n$|
|$24$|$\le 100000$|$\le 1000000000$|$\le n$|
|$25$|$\le 100000$|$\le 1000000000$|$\le n$|
所有测试点均满足 $0\le m\le 10^9,1\le n\le 10^9,1\le D\le 10^5$。
|:-:|:-:|:-:|:-:|
|$1$|$\le 2$|$\le 10$|$\le n$|
|$2$|$\le 2$|$\le 20$|$\le n$|
|$3$|$\le 100$|$\le 100$|$\le n$|
|$4$|$\le 100$|$\le 100$|$\le n$|
|$5$|$\le 100$|$\le 100$|$\le n$|
|$6$|$\le 100$|$\le 100$|$\le n$|
|$7$|$\le 100$|$\le 100$|$\le n$|
|$8$|$\le 4000$|$\le 4000$|$\le n$|
|$9$|$\le 4000$|$\le 4000$|$\le n$|
|$10$|$\le 4000$|$\le 4000$|$\le n$|
|$11$|$\le 4000$|$\le 4000$|$\le n$|
|$12$|$\le 4000$|$\le 4000$|$\le n$|
|$13$|$\le 300$|$\le 1000000000$|$\le n$|
|$14$|$\le 300$|$\le 1000000000$|$\le n$|
|$15$|$\le 300$|$\le 1000000000$|$\le n$|
|$16$|$\le 100000$|$\le 1000000000$|$\le 0$|
|$17$|$\le 100000$|$\le 1000000000$|$\le 1$|
|$18$|$\le 100000$|$\le 1000000000$|$\le 2$|
|$19$|$\le 100000$|$\le 1000000000$|$\le n$|
|$20$|$\le 100000$|$\le 1000000000$|$\le n$|
|$21$|$\le 100000$|$\le 1000000000$|$\le n$|
|$22$|$\le 100000$|$\le 1000000000$|$\le n$|
|$23$|$\le 100000$|$\le 1000000000$|$\le n$|
|$24$|$\le 100000$|$\le 1000000000$|$\le n$|
|$25$|$\le 100000$|$\le 1000000000$|$\le n$|
所有测试点均满足 $0\le m\le 10^9,1\le n\le 10^9,1\le D\le 10^5$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？