← 返回题目列表

Codeforces · 1776/K

K. 统一化学

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

在平行宇宙中有$$$n$$$种化学元素,编号从$$$1$$$到$$$n$$$。编号为 $$$n$$$ 的元素迄今为止尚未被发现,它的发现将成为研究的顶峰,并将为发现者带来永恒的声誉和所谓的 SWERC 奖。

有 $$$m$$$ 独立研究人员,编号从 $$$1$$$ 到 $$$m$$$,正在试图发现它。目前,第 $$$i$$$ 位研究人员拥有元素 $$$s_i$$$ 的样本。每年,每位研究人员独立进行一次聚变实验。在融合实验中,如果研究人员当前有元素 $$$a$$$ 的样本,他们会生成在 $$$a+1$$$ 和 $$$n$$$ 之间均匀随机选择的元素 $$$b$$$ 的样本,并丢失元素 $$$a$$$ 的样本。不同研究人员或不同年份发现的元素是完全独立的。

第一个发现元素 $$$n$$$ 的研究人员将获得 SWERC 奖。如果多名研究人员在同一年发现了该元素,他们都会获得该奖。对于每个 $$$i = 1, \, 2, \, \dots, \, m$$$,您需要计算第 $$$i$$$ 位研究人员获奖的概率。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^{18}$$$, $$$1 \le m \le 100$$$) — 元素数量和研究人员数量。

第二行包含 $$$m$$$ 整数 $$$s_1, \, s_2, \, \dots, \, s_m$$$ ($$$1 \le s_i < n$$$) — 研究人员当前拥有的元素。

输出

打印 $$$m$$$ 浮点数。第 $$$i$$$ 个数字应该是第 $$$i$$$ 个研究人员赢得 SWERC 奖的概率。如果每个数字与正确数字最多相差 $$$10^{-8}$$$,则您的答案被接受。

示例

输入 #1

2 3
1 1 1

输出 #1

1.0 1.0 1.0

输入 #2

3 3
1 1 2

输出 #2

0.5 0.5 1.0

输入 #3

3 3
1 1 1

输出 #3

0.625 0.625 0.625

输入#4

100 7
1 2 4 8 16 32 64

输出#4

0.178593469 0.179810455 0.182306771
0.187565366 0.199300430 0.229356322
0.348722518

注意

在第一个样本中,所有研究人员将在第一年发现元素 $$$2$$$ 并赢得 SWERC 奖。

在第二个样本中,最后一位研究员一定会在第一年发现元素 $$$3$$$ 并获得 SWERC 奖。前两名研究人员有 $$$50\%$$$ 的机会发现元素 $$$2$$$ 和 $$$50\%$$$ 的机会发现元素 $$$3$$$,只有元素 $$$3$$$ 才能为他们带来奖金。

在第三个样本中,每个研究人员在第一年都有独立的 $$$50\%$$$ 机会发现元素 $$$3$$$,在这种情况下他们肯定会赢得 SWERC 奖。另外,如果他们在第一年都发现了元素$$$2$$$,即$$$12.5\%$$$的机会,那么他们将在第二年都发现元素$$$3$$$并全部获奖。