310057: CF1776K. Uniform Chemistry
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Uniform Chemistry
题目描述
In a parallel universe there are $ n $ chemical elements, numbered from $ 1 $ to $ n $ . The element number $ n $ has not been discovered so far, and its discovery would be a pinnacle of research and would bring the person who does it eternal fame and the so-called SWERC prize. There are $ m $ independent researchers, numbered from $ 1 $ to $ m $ , that are trying to discover it. Currently, the $ i $ -th researcher has a sample of the element $ s_i $ . Every year, each researcher independently does one fusion experiment. In a fusion experiment, if the researcher currently has a sample of element $ a $ , they produce a sample of an element $ b $ that is chosen uniformly at random between $ a+1 $ and $ n $ , and they lose the sample of element $ a $ . The elements discovered by different researchers or in different years are completely independent. The first researcher to discover element $ n $ will get the SWERC prize. If several researchers discover the element in the same year, they all get the prize. For each $ i = 1, \, 2, \, \dots, \, m $ , you need to compute the probability that the $ i $ -th researcher wins the prize.输入输出格式
输入格式
The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 10^{18} $ , $ 1 \le m \le 100 $ ) — the number of elements and the number of researchers. The second line contains $ m $ integers $ s_1, \, s_2, \, \dots, \, s_m $ ( $ 1 \le s_i < n $ ) — the elements that the researchers currently have.
输出格式
Print $ m $ floating-point numbers. The $ i $ -th number should be the probability that the $ i $ -th researcher wins the SWERC prize. Your answer is accepted if each number differs from the correct number by at most $ 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说明
In the first sample, all researchers will discover element $ 2 $ in the first year and win the SWERC prize. In the second sample, the last researcher will definitely discover element $ 3 $ in the first year and win the SWERC prize. The first two researchers have a $ 50\% $ chance of discovering element $ 2 $ and a $ 50\% $ chance of discovering element $ 3 $ , and only element $ 3 $ will bring them the prize. In the third sample, each researcher has an independent $ 50\% $ chance of discovering element $ 3 $ in the first year, in which case they definitely win the SWERC prize. Additionally, if they all discover element $ 2 $ in the first year, which is a $ 12.5\% $ chance, then they will all discover element $ 3 $ in the second year and all win the prize.Input
题意翻译
给定 $n$ 个元素，$m$ 个人，每个人有一个初始元素 $s_i$。 每人在每个时间单位中都会进行一次实验，可以等概率的把元素 $a$ 变成 $a_{i+1},a_{i+2},\dots,n$ 中的任意一个。 求每个人最先把自己的元素变成元素 $n$ 的概率。若多人在同一时间单位变出了元素 $n$，那么称每一个人都为“最先”。Output
**题目描述**
在一个平行宇宙中，有 $ 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 $ 个研究者赢得 SWERC 奖的概率。
**输入输出格式**
**输入格式**
第一行包含两个整数 $ 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 $ 并都赢得奖项。**题目描述** 在一个平行宇宙中，有 $ 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 $ 个研究者赢得 SWERC 奖的概率。 **输入输出格式** **输入格式** 第一行包含两个整数 $ 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 $ 并都赢得奖项。
在一个平行宇宙中，有 $ 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 $ 个研究者赢得 SWERC 奖的概率。
**输入输出格式**
**输入格式**
第一行包含两个整数 $ 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 $ 并都赢得奖项。**题目描述** 在一个平行宇宙中，有 $ 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 $ 个研究者赢得 SWERC 奖的概率。 **输入输出格式** **输入格式** 第一行包含两个整数 $ 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 $ 并都赢得奖项。