#P40006. 2019 ICPC NCNA Regional Contest G - Birthday Paradox

2019 ICPC NCNA Regional Contest G - Birthday Paradox

题目描述

image.png

The probability of n unique birthdays among n people.

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 nn where 1n3651 \le n \le 365. The second line contain integers c1c_1 through cnc_n, where 1ci1001 \le c_i \le 100 for all cic_i. The value cic_i 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 bb of observing a group of people with the given distribution of shared birthdays. Since bb may be quite small, output instead log10(b)\log_{10}(b). Your submission's answer is considered correct if it has an absolute or relative error of at most 10610^{-6} 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 P=2P=2 people with distinct birthdays. The probability of this occurring is b=364/3650.9972602740b = 364/365 \approx 0.9972602740, and log10(b)0.001191480807419\log_{10}(b) \approx -0.001191480807419.

    The second sample case represents the third example in the list given earlier with P=10P=10 people. In this case, the probability is b0.0000489086b \approx 0.0000489086, and log10(b)4.310614508857128\log_{10}(b) \approx -4.310614508857128.