← 返回题目列表

AtCoder · abc404_f

I. 丢失和重磅

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

有 N 按钮。其中一个是获胜按钮,另一个是 N-1 正在丢失按钮。

Aoki 知道哪个按钮获胜,但 Takahashi 不知道。另外,高桥也无法区分 N 按钮。

他们使用这些按钮玩游戏。游戏包括重复以下序列 T 次:

  1. 青木安排 N 按钮按随机顺序排列。
  2. Takahashi 执行操作“选择一个按钮并按下” M 次。他可以多次选择同一个按钮。
  3. 青木告诉高桥自游戏开始以来到目前为止按下获胜按钮的次数。

当且仅当获胜按钮被按下至少 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