BirthdayParadox

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 $50\%$ 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.

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 n where $1 \le n \le 365$ . The second line contain integers $c_1$ through $c_n$ , where $1 \le c_i \le 100$ for all $c_i$ . The value $c_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 b of observing a group of people with the given distribution of shared birthdays. Since b may be quite small, output instead $\log_{10}(b)$ . Your submission's answer is considered correct if it has an absolute or relative error of at most $10^{-6}$ from the judge's answer.

from math import log10 JC = [0] for i in range(1,365*101): JC.append(JC[-1]+log10(i)) def C(m,n): return JC[m]-JC[n]-JC[m-n] n = int(input()) ls = input().split(' ') ls = [int(i) for i in ls] sm=sum(ls) a=C(365,n) b=365 hav = 0 for i in range(1,101): cur = ls.count(i) if cur != 0: a += C(n-hav,cur) hav += cur hav = 0 for i in ls: a += C(sm-hav,i) hav += i print(a-sm * log10(b)) # x=10**(-4.310614508857128+log10(b))//A(365,7) # print(x)

#include<cstdio> #include<cmath> int cnt[105]; double lfrac[40000]; int main() { int n,i,c,C = 0; double ans; for(i=2;i<40000;i++)lfrac[i] = lfrac[i-1]+log10(i); scanf("%d",&n); ans = lfrac[365]-lfrac[365-n]; while(n--) { scanf("%d",&c), C += c, cnt[c]++; ans -= lfrac[c]; } for(i=1;i<=100;i++)ans -= lfrac[cnt[i]]; ans = ans+lfrac[C]-C*log10(365); printf("%.9lf",ans); return 0; }

详情