kmjp's blog

競技プログラミング参加記です

Codeforces #369 Div2 E. ZS and The Birthday Paradox

Codeforces

まぁ解けて良かった。
http://codeforces.com/contest/711/problem/E

問題

この星では1年が(2^N)日ある。
その場にK人の人がいる。各人の誕生日は等確率でで(2^N)日のいずれかであるとき、２名以上の誕生日が一致する確率pを求めたい。
p=A/Bと既約分数として有理数表記したとき、A%M, B%M (M=1000003)を答えよ。

解法

K>2^Nの時は人が日数より多いのでp=1のため、1/1を答えればよい。
そうでない場合、解は \displaystyle 1 - \prod_{i=0}^{K-1} \frac{2^N - i}{2^N} = 1 - \frac{\prod_{i=0}^{K-1}(2^N - i)}{(2^N)^K}

S=2^Nとし、右の式の分子をP,分母をQとする。P'=Q-PとするとP'/Qを約分すれば解になる。
まず約分は後回しにして、まずP,Qを考える。
Q=S^Kなのでこれは容易に求められる。

次にPだが、この問題はMがいつもの10^9+7ではなく10^6+3と小さいことを思い出そう。
K≧Mなら乗算の過程で必ずMの倍数が１つはあるので、P%M=0としてよい。
K＜MならO(K)回乗算を行ってPを求めればよい。

これでP,Q及びP'が求められる。
後はこれを約分することを考える。P+P'=Qなので、P/QとP'/Qは同じ数で分子分母割って約分できることがわかる。
ではP/Qはどんな数で約分できるか。
分母は2の累乗なので、分母[tex: \displaystyle \frac{\prod_{i=0}^{K-1}(2^N - i)}が2の何乗であるかを考える。
最初の項は2^Nなので2^Nで割れる。
それ以外の項では、2で割れるものが(K-1)/2個、4で割れるものが(K-1)/4個…2^iで割れる者が(K-1)/(2^i)個…と考えると、分子分母何で割れば既約分数にできるかわかる。

ll N,K;
ll mo=1000003;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	if(N<=60 && 1LL<<N<K) return _P("1 1\n");
	
	ll A=1;
	ll T=modpow(2,N);
	ll B=modpow(T,K);
	FOR(i,K) {
		A = A * (T+mo-i) % mo;
		if(A==0) break;
	}
	
	A = (B - A + mo) % mo;
	(A *= modpow(T))%=mo;
	(B *= modpow(T))%=mo;
	for(i=1;i<=60;i++) {
		ll n=(K-1)>>i;
		ll revrev = modpow(2);
		
		(A *= modpow(revrev,n))%=mo;
		(B *= modpow(revrev,n))%=mo;
	}
	
	cout<<A<<" "<<B<<endl;
}

まとめ

Mが小さいので、一時的に途中式でO(M^3)な値が出てくるのかと思ったら違った。