#P18832. [COCI 2026/2027 #2] Jackpot
[COCI 2026/2027 #2] Jackpot
题目描述
键盘上有 种字符。每按一次回车,恰有一种字符被写入,或者什么也不写:写入字符 的概率是 ,剩余概率对应不写字符。各次按键独立。
如果每种字符 都已出现至少 次,就达成目标。求从空字符串出发,首次达成目标所需的按键次数的期望。
输入格式
第一行一个整数 。第二、三、四行分别给出 、、。
输出格式
若无法达成目标,输出 nikada。否则设期望为既约分数 ,输出 。
数据范围与评分
- ,,。
- ,,。
- 若目标可达,任选一个非空的、仅含 的字符集合,其概率之和化为既约分数后,分子不被 整除。
- 时间限制 5 秒,内存限制 8 MiB。
| 子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 9 | |
| 2 | 26 | |
| 3 | 39 | |
| 4 | 31 | 每个 |
| 5 | 无 | |
输入输出样例
样例 1
输入
1
1
1
6
输出
6
样例 2
输入
2
1 1
1 1
2 2
输出
3
样例 3
输入
1
1
0
6
输出
nikada