Birthday Paradox(简单生日概率)

vj传送

一眼看过去发现就是个概率题目

有$m$个人,一年有$n$天

假如所有人生日都不在同一天,选法是$C_n^m\ast m!$

而总选法是每个人都有$n$种选法m就是$n^m$

概率是$\frac{C_n^m\ast m!}{n^m}$

然后换种思想,直接求所有人生日不同天的概率,就是

$\frac{n}{n}\ast \frac{n-1}{n}\ast \frac{n-2}{n}...\ast \frac{n-m+1}{n}$

发现和上面的式子是一样的,随便乱推都能推到

可以二分求,但是这精度…而且会爆$double$

然而…居然能过,数据太水还是咋的…

#include <bits/stdc++.h> using namespace std; int main() { int t,casenum=0,n; cin >> t; while( t-- ) { cin >> n; int ans=1; double p=1; for(int j=n-1;j>=1;j--) { p = p*j/n; if( p<=0.5 ) break; ans++; } printf("Case %d: %d\n",++casenum,ans); } }