BOJ 13182 제비

문제 링크입니다.

문제 요약

상자에 $R$개의 빨강 제비, $G$개의 초록 제비, $B$개의 파랑 제비가 있습니다. 파랑 제비를 $K$번 뽑을 때까지 다음의 시행을 반복합니다.

• 제비를 무작위로 하나 뽑아, 빨간색이면 버리고 아니면 다시 상자에 집어넣습니다.

총 시행 횟수 = 행동이 끝날 때까지 제비를 뽑은 횟수의 기댓값을 구하세요.

풀이

파랑 제비를 뽑은 횟수는 문제 조건 상 반드시 $K$입니다. 이제 초록 제비와 파랑 제비만 있는 상황을 생각해 봅시다. 제비를 뽑을 때마다 해당 제비의 색을 써내려간다고 생각하면, 중간에 빨간 제비가 있든 없든 초록-파랑의 나열에서 $K$번째 파랑이 나올 때까지 초록 또는 파랑색의 제비를 뽑는 횟수의 기댓값은 동일함을 직관적으로 알 수 있습니다.

$G$개의 초록 제비와 $B$개의 파랑 제비가 있을 때, 파랑 제비가 하나 나오기 전까지 뽑히는 초록 제비 개수의 기댓값은 ${B+G \over B} - 1 = {G \over B}$이고, 이 행동을 총 $K$번 반복하므로 초록 제비와 파랑 제비의 기댓값 합은 $K({G \over B}+1)$입니다.

빨강 제비는 초록 제비나 다른 빨강 제비와 관계없이, 파랑 제비들과의 뽑히는 순서에 의해서만 시행 중 뽑힐지 말지가 결정됩니다. 하나의 빨강 제비가 뽑힐 확률은, 전체집합에서 그 빨강 제비가 뽑히지 않는 경우의 비율을 빼 구할 수 있습니다. 빨강 제비 하나와 $B$개의 파랑 제비만 있는 경우에서 고려해도 독립 조건에 의해 같은 확률을 얻을 수 있으며, 이는 $1-({B \over B+1})^K$가 됩니다. 빨강 제비가 총 $R$개이므로 모든 빨강 제비에 의해 얻게 되는 기댓값은 $R(1-({B \over B+1})^K)$입니다.

위의 두 값을 더하면 답을 구할 수 있습니다.

코드

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

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;
}

void solve(){
	ll r, g, b, k; cin >> r >> g >> b >> k;
	ll ans = r*(mod+1-pw(b*pw(b+1,mod-2)%mod,k))%mod;
	ans = (ans+k*g%mod*pw(b, mod-2)%mod+k)%mod;
	cout << ans << '\n';
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T; cin >> T; while(T--) solve();
}