Codeforces 26 D. Tickets

問題

10円のチケットをn+m枚販売する。

この国には10円と20円の二つの硬貨しかなく、
10円のみを持った客がn人、20円のみを持った客がm人来るものとする。
手元にはk枚の10円がある。

客がランダムな順番で来るとき、全ての客におつりをきちんと返せる確率はいくつか求めよ。

制約条件

n,m≦100000
k≦10

方針

nxmの格子を(0,0)の点Aから(n-1,m-1)の点Bへ行く問題に帰着される。
手元にk枚の10円があるということは、
格子の(0,k+1), (1,k+2), ……より上側の点のみを通ってゴールへ行くことに相当する。

これは、ゴールの点Bを(0,k+1),(1,k+2)……の点について折り返した点をB'とすると、
(AからBへ行く場合の数)-(AからB'へ行く場合の数)が、
有効な場合の数である。

それぞれはコンビネーションにより求まる。
コンビネーションはあらかじめ階乗を計算しておけばO(1)で求まる。
ここではn+m≦200000と大きいので、
対数を取って計算しておき、最後にe^xにする。

ソースコード

double lf[200001];
double lc(int n,int k){
	return lf[n]-lf[k]-lf[n-k];
}
void run()
{
	int n,m,k;
	cin>>n>>m>>k;
	rep(i,200000)lf[i+1]=lf[i]+log(i+1);
	if(m<=k){
		cout<<1<<endl;
		return;
	}
	if(n+k<m){
		cout<<0<<endl;
		return;
	}
	double a=lc(n+m,m-k-1)-lc(n+m,n);
	printf("%.9f\n",1-exp(a));
}