Birthday Paradox(简单生日概率)

vj传送

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

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

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

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

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

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

$\frac{n}{n}?\frac{n?1}{n}?\frac{n?2}{n}...?\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);}
}