分数: 550 点
问题陈述
有 N 按钮。其中一个是获胜按钮,另一个是 N-1 正在丢失按钮。
Aoki 知道哪个按钮获胜,但 Takahashi 不知道。另外,高桥也无法区分 N 按钮。
他们使用这些按钮玩游戏。游戏包括重复以下序列 T 次:
- 青木安排 N 按钮按随机顺序排列。
- Takahashi 执行操作“选择一个按钮并按下” M 次。他可以多次选择同一个按钮。
- 青木告诉高桥自游戏开始以来到目前为止按下获胜按钮的次数。
当且仅当获胜按钮被按下至少 K 次全程 T 重复。
求高桥在最大化其获胜概率时获胜的概率。
约束
- 1 \le N \le 2\times 10^5
- 1 \le T \le 30
- 1 \le M \le 30
- 1 \le K \le 30
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N T M K
输出
输出答案。如果您的输出与真实答案的绝对或相对误差最多为 10^{-6}.
示例输入 1
3 2 2 3
示例输出 1
0.222222222222222
游戏可以按如下方式进行(不一定是最佳的):
- 第一次重复
- 青木随机排列按钮,使获胜按钮位于 位置 1,失败按钮位于位置 2 和 3.
- 高桥按下按钮 1.
- 高桥按下按钮 2.
- 青木告诉他获胜按钮已被按下 1 时间。
- 第二次重复
- 青木随机排列按钮,使获胜按钮位于 位置 3,失败按钮位于位置 1 和 2.
- 高桥按下按钮 3.
- 高桥按下按钮 3.
- 青木告诉他获胜按钮已被按下 3 次。
- 由于获胜按钮被按下不少于 3 次,高桥获胜。
这种情况下的真实答案是 \tfrac{2}{9},所以输出如下 0.222222 or 0.222223141592 也被接受。
示例输入 2
10 1 10 1
示例输出 2
1.000000000000000
示例输入 3
100 10 10 2
示例输出 3
0.401263060761621