#P40006. 2019 ICPC NCNA Regional Contest G - Birthday Paradox
2019 ICPC NCNA Regional Contest G - Birthday Paradox
题目描述
The Birthday Paradox is the name given to the surprising fact that if there are just 23 people in a group, there is a greater than chance that a pair of them share the same birthday. The underlying assumptions for this are that all birthdays are equally likely (which isn't quite true), the year has exactly 365 days (which also isn't true), and the people in the group are uniformly randomly selected (which is a somewhat strange premise). For this problem, we'll accept these assumptions.
Consider what we might observe if we randomly select groups of P=10 people. Once we have chosen a group, we break them up into subgroups based on shared birthdays. Among many other possibilities, we might observe the following distributions of shared birthdays:
- all 10 have different birthdays, or
- all 10 have the same birthday, or
- 3 people have the same birthday, 2 other people have the same birthday (on a different day), and the remaining 5 all have different birthdays. </ul> Of course, these distributions have different probabilities of occurring.
Your job is to calculate this probability for a given distribution of people sharing birthdays. That is, if there are P people in a group, how probable is the given distribution of shared birthdays (among all possible distributions for P people chosen uniformly at random)?
输入格式
The first line gives a number where . The second line contain integers through , where for all . The value represents the number of people who share a certain birthday (and whose birthday is distinct from the birthdays of everyone else in the group).
输出格式
Compute the probability of observing a group of people with the given distribution of shared birthdays. Since may be quite small, output instead . Your submission's answer is considered correct if it has an absolute or relative error of at most from the judge's answer.
样例
输入样例1
2 1 1
输出样例1
-0.001191480807419
输入样例2
7 1 1 2 1 3 1 1
输出样例2
-4.310614508857128
数据范围与提示
The first sample case shows people with distinct birthdays. The probability of this occurring is , and .
The second sample case represents the third example in the list given earlier with people. In this case, the probability is , and .