ABC003 D - AtCoder社の冬

D - AtCoder社の冬

概要

R * CマスのうちのX * Yマス内にデスクをD個、サーバーラックをL個置く。
このとき、X * Yマス内の最も外側の4辺にはそれぞれ、デスクもしくはサーバーラックが置かれているものとする。
このような置き方（X * Yマスの選び方、デスク・サーバーラックの置き方）が何通りあるか答えよ。(mod 10^9 + 7)

制約

1 <= R, C <= 30
1 <= X <= R, 1 <= Y <= C
D, L >= 0
1 <= D+L <= X * Y

方針

X * Yマスをどこにするかは(R - X + 1) * (C - Y + 1)通り。
それぞれについて、デスクとサーバーラックの置き方を考える。

もしX * Y = D + L であれば、置き方はcomb(X * Y, D)通り。（部分点解法）

X * Y > D + L のときを考える。このとき必要な置き方は、外側4辺にそれぞれデスクもしくはサーバーラックを置くことである。
ここで包除原理を使う。すなわち以下の通り。

U:すべての場合
P:上辺にデスクとサーバーラックがない
Q:左辺にデスクとサーバーラックがない
R:下辺にデスクとサーバーラックがない
S:右辺にデスクとサーバーラックがない
とすると、求める事象は
U - (P | Q | R | S)
= U - (P + Q + R + S) + (P & Q + P & R + P & S + Q & R + Q & S + R & S)
- (P & Q & R + P & R & S + P & Q & S + Q & R & S) + P & Q & R & S
となる。

実装としては、4ビットの各桁について1桁目はP、2桁目はQ、のように対応付け、
16通りの事象の組み合わせをそれぞれ計算させる。

感想

下記を参考にしました。
tutuz.hateblo.jp

解答

Submission #4136198 - AtCoder Beginner Contest 003

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
using namespace std;
typedef long long ll;
 
const ll MOD = 1e9 + 7;
const ll max_n = 20000;
ll fact[max_n];
bool fact_init = false;
 
ll pow(ll a, ll b){
	if(b == 0) return 1;
	if(b % 2 == 1) return a * pow(a, b - 1) % MOD;
 
	ll d = pow(a, b / 2) % MOD;
	return d * d % MOD;
}
 
ll comb(ll n, ll k){
	if(!fact_init){
		fact[0] = 1;
		fact[1] = 1;
 
		for(ll i = 2; i <= max_n; i++){
			fact[i] = fact[i-1] * i;
			fact[i] %= MOD;
		}
 
		fact_init = true;
	}
 
	ll ret = fact[n];
	ret *= pow(fact[k],MOD-2);
	ret %= MOD;
	ret *= pow(fact[n-k],MOD-2);
	ret %= MOD;
	return ret;
 
	// X^(-1) = X^(p-2) (mod p) (Fermat's little theorem)
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll R, C;
	cin >> R >> C;
 
	ll X, Y;
	cin >> X >> Y;
 
	ll D, L;
	cin >> D >> L;
 
	ll ans = 0;
	rep(b, 1 << 4){
		ll tx = X;
		ll ty = Y;
 
		if((b >> 0) & 1) tx--;
		if((b >> 1) & 1) ty--;
		if((b >> 2) & 1) tx--;
		if((b >> 3) & 1) ty--;
 
		if(tx < 0 || ty < 0) continue;
		if(tx * ty < D + L) continue;
 
		int bsum = 0;
		rep(i, 4) if((b >> i) & 1) bsum++;
 
		if(bsum % 2 == 0){
			ans += comb(tx * ty, D + L) * comb(D + L, D);
			ans %= MOD;
		}else{
			ans += MOD;
			ans -= comb(tx * ty, D + L) * comb(D + L, D) % MOD;
			ans %= MOD;
		}
	}
 
	ans *= (R - X + 1) * (C - Y + 1);
	ans %= MOD;
 
	cout << ans << endl;
}