BOJ 22402 野球観戦

문제 링크입니다.

요약

X팀과 Y팀이 야구 경기를 진행합니다. A번의 경기에서는 X팀이 이기고, B번의 경기에서는 Y팀이 이기고, C번의 경기에서는 무승부가 나게끔 하면서 X팀은 총 Sx 점, T팀은 총 Sy 점을 얻게 되는 경기 결과의 수를 구하세요.

경기 배치

점수가 배정되지 않은 상태에서 경기는 A, B, C의 세 종류가 있습니다. 이를 나열하는 방법의 수는 $\binom{A+B+C}{A} \binom{B+C}{B}$ 입니다. 경기 종류의 순서를 결정하고 나면, 종류 별로 A1, A2, … , Aa와 같이 먼저 치룰 경기부터 순서대로 번호를 매길 수 있습니다. 즉 순서를 결정한 이후로는 모든 경기를 서로 다른 것으로 간주할 수 있습니다.

이겨 놓기

한 팀이 각 경기에서 얻는 점수를 두 가지로 분류할 수 있습니다. 하나는 상대 팀의 점수와 상쇄되는 점수, 다른 하나는 상대의 점수보다 넘치게 받는 점수입니다. X팀을 기준으로 설명하면, X팀이 받는 넘치는 점수는 모두 A타입 경기에 들어가야 하고, 각 A타입 경기에는 넘치는 점수가 적어도 1점씩 들어가야 합니다. 넘치는 점수가 총 x점이라고 하면, 먼저 각 팀에 1점을 분배하고 남은 x-A점을 각 A타입 경기에 분배하는 방법의 수는 ${}{A}H{x-A}$입니다. 같은 방식으로 Y팀이 받는 넘치는 점수 y점을 B타입 경기에 분배하는 경우의 수는 ${}{B}H{y-B}$입니다.

남은 점수 털기

X팀이 받은 총 점수와 Y팀이 받은 총 점수에서 각자가 받은 넘치는 점수를 제하면 남은 점수는 서로 같아야 합니다. 이에 따라 x를 결정하면 y 역시 자동으로 결정됨을 알 수 있습니다.

남은 점수는 두 팀이 같은 경기에서 같은 양을 얻어야만 합니다. 이 값을 z라고 하면, z점을 전 경기에 걸쳐 털어내는 방법의 수는 ${}{A+B+C}H{z}$입니다.

각 x마다의 경우의 수를 구해 모두 합하면 답을 얻을 수 있습니다. 팩토리얼과 그 모듈러 곱셉 역원 값을 전처리함으로써, 각 x마다 필요한 값을 $\mathcal{O}(1)$에 구할 수 있습니다. 총 시간 복잡도는 테스트 케이스 당 $\mathcal{O}(A+B+C+S_X+S_Y)$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll mod = 1e9+7;

ll fac[5050505], inv[5050505];

ll pw(ll n, ll r){
	ll ret = 1;
	while(r){
		if(r&1) ret = ret*n%mod;
		n = n*n%mod;
		r >>= 1;
	}
	return ret;
}

inline ll C(ll n, ll r){
	if(r < 0 || r > n) return 0;
	return fac[n]*inv[r]%mod*inv[n-r]%mod;
}

inline ll H(ll n, ll r){
	if(!n && !r) return 1;
	return C(n+r-1, r);
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	fac[0] = 1;
	for(ll i = 1; i <= 5000000; i++){
		fac[i] = fac[i-1]*i%mod;
	}
	inv[5000000] = pw(fac[5000000], mod-2);
	for(ll i = 5000000; i; i--){
		inv[i-1] = inv[i]*i%mod;
	}
	while(1){
		ll a, b, c, x, y; cin >> a >> b >> c >> x >> y;
		if(!(a||b||c||x||y)) return 0;
		ll ord = C(a+b+c, a)*C(b+c, b)%mod;
		ll ans = 0;
		for(ll i = a; i <= x; i++){
			ll j = y-x+i;
			if(j < b || j > y) continue;
			ans += H(a, i-a)*H(b, j-b)%mod*H(a+b+c, x-i)%mod;
			ans %= mod;
		}
		cout << ans*ord%mod << '\n';
	}
}