Codeforces #399 F. Barrels and boxes

しょうもないミスで落とす…。
http://codeforces.com/contest/768/problem/F

問題

F個の食べ物が入った箱と、W個のワインが入った箱がある。
これらを一列に並べよう。

その際、同じ種類の箱は縦に積むことができる。
また、横に並ぶ箱同士は異なる種類でなければならない。

全並べ方のうち、ワインの入った箱はすべてH個より高く積まれているようなものの割合を答えよ。
具体的には、条件を満たす並べ方をp通り、全並べ方をq通りとしたとき、p*q^-1 mod (10^9+7)を答えよ。

解法

素数Mと整数a,bに対しaM+b % M = bは成り立つが、同様に1/(cM + d) = 1/d (mod M)もd!=0であれば成り立つ。
1/d = e (mod M)とすると(cM + d)*e = ceM + de = 1 (mod M)のためである。

よって、p,qはそれぞれmod Mで考えればよい。
q % M == 0の場合はこの考え方はできないが、幸い今回のケースでqはそうならない。
すべての箱の並べ方を考えると、結局適当に箱を並べて、隣接する箱が同じ種類なら縦に積んでいくと考えれば結局q = Comb(F+W, F)なので、今回のF,Wの範囲ではqは10^7の倍数にはならない。

次にpを考える。
食べ物の箱の列数Aを総当たりしよう。その場合、食べ物の箱の並べ方は[tex: {}_F H_A}通りである。
このとき、ワインの箱の並べ方は(B+1),B,(B-1)列のいずれかである。またB列の場合は2通り考えられる。

たとえばワインをB列作る場合、それぞれが(H+1)個以上の高さになる場合はどうするか。
まず固定で各列に(H+1)個箱を配置し、残ったW-B(H+1)個に対して重複組み合わせを用いて組み合わせを求めればよい。

以下のコードはqはComb(F+W,F)ではなくpと同様に組み合わせ数の総和を計算している。

ll F,W,H;
ll mo=1000000007;

ll combi(ll N_, ll C_) {
	const int NUM_=600001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { 
	if(P_<0 || Q_<0) return 0;
	if(P_==0) return Q_==0;
	if(Q_==0) return 1;
	return combi(P_+Q_-1,Q_);
}

ll modpow(ll a, ll n) {
	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>>F>>W>>H;
	
	if(F==0) {
		cout<<(W>H)<<endl;
		return;
	}
	
	ll P=0,Q=0;
	for(ll i=1;i<=F;i++) {
		ll a=hcomb(i,F-i);
		ll b=(2*hcomb(i,W-i)+hcomb(i+1,W-(i+1))+hcomb(i-1,W-(i-1)))%mo;
		ll c=(2*hcomb(i,W-i*(H+1))+hcomb(i+1,W-(i+1)*(H+1))+hcomb(i-1,W-(i-1)*(H+1)))%mo;
		
		(P += a*c)%=mo;
		(Q += a*b)%=mo;
	}
	P = P * modpow(Q,mo-2) % mo;
	cout<<P<<endl;
	
}

まとめ

F=0のときのミスとオーバーフローのミスという、しょうもないミスでTシャツを逃した。