← 返回题目列表

Codeforces · 457/D

D. 宾果游戏!

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

宾果游戏是在 5 × 5 方格上进行的,其中填充了 1 到 75 之间的不同数字。在本问题中,您将考虑在 n × n 网格上进行的通用版本,其中包含 1 到 m (m ≥ n2) 之间的不同数字。

玩家首先选择随机生成的宾果网格(在所有可用网格中统一生成)。然后将随机调用 1 到 m 之间的 k 个不同的数字(在所有可用的 k 个数字集合中统一调用)。对于出现在网格上的每个被叫号码,玩家标记该单元格。最后的分数是 2 的幂(完全标记的行数加上完全标记的列数)。

确定分数的期望值。预期分数可能会很大。如果预期分数大于 1099,则打印 1099(例如,不带引号的“1e99”)。

输入

输入将由三个整数 n、m、k 组成(1 ≤ n ≤ 300;n2 ≤ m ≤ 100000;n ≤ k ≤ m)。

输出

打印 1099 和预期分数中较小的一个。您的答案必须正确,绝对误差或相对误差在 10 - 9 之间。

示例

输入 #1

1 2 1

输出 #1

2.5

输入 #2

2 4 3

输出 #2

4

输入 #3

7 59164 40872

输出 #3

3.1415926538