[BOJ 26078 // C++] 곰곰이와 토너먼트

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26078번 문제인 곰곰이와 토너먼트이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/26078 

26078번: 곰곰이와 토너먼트

곰곰이가 i번째 라운드의 상금을 탈 수 있을 확률은 곰곰이가 i번째 라운드까지 진출하고 그 상대를 이길 수 있을 확률, 즉 곰곰이를 제외한 참가자 \(2^k-1\)명 중 \(2^i-1\)명을 뽑을 때 그 뽑은 참가자들의 춤 실력 지표가 곰곰이의 춤 실력 지표보다 낮을 확률과 같다는 점을 관찰하자. 이는 참가자들 중 곰곰이의 춤 실력 지표보다 낮은 실력 지표를 가진 참가자들의 수를 미리 알아두면 조합(combination)의 계산을 통해 계산해낼 수 있다.

 

위에서 구한 확률을 이용해 i번째 라운드의 상금에 대한 기댓값을 구할 수 있다. 이 기댓값은 분모를 \((2^k-1)!\)로 하는 분수로 항상 표현할 수 있고 이 수와 998244353은 서로소이므로 이 분수의 분모와 분자를 각각 x와 y로 삼아 문제를 해결할 수 있다.

 

998244353이 소수임을 이용하면 조건을 만족하는 \(z\)의 값을 페르마의 소정리(Fermat's Little Theorem)와 binary exponentiation을 이용해 구할 수 있다.

 

아래는 제출한 소스코드이다.

#define MOD 998244353
#include <iostream>
using namespace std;
typedef long long ll;

ll fact[262145];
ll invfact[262145];

void init() {
	fact[0] = fact[1] = 1;
	for (ll i = 2; i < 262145; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
	}
	invfact[0] = invfact[1] = 1;
	for (ll i = 2; i < 262145; i++) {
		invfact[i] = MOD - ((MOD / i) * invfact[MOD % i]) % MOD;
	}
	for (int i = 2; i < 262145; i++) {
		invfact[i] = (invfact[i] * invfact[i - 1]) % MOD;
	}
}

ll N, N2;
ll A, B;
ll arr[18];

ll x;
ll cnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	init();

	cin >> N; N2 = (1 << N) - 1;
	cin >> x;
	for (int i = 0; i < N2; i++) {
		ll tmp; cin >> tmp;
		if (tmp < x) cnt++;
	}

	B = fact[N2];

	for (ll i = 1; i <= N; i++) {
		ll r; cin >> r;
		ll i2 = (1 << i) - 1;
		if (i2 > cnt) break;
		A += ((fact[cnt] * invfact[cnt - i2]) % MOD) * ((fact[N2 - i2] * r) % MOD);
		A %= MOD;
	}

	int X = MOD - 2;
	ll inv = 1;
	while (X) {
		if (X & 1) inv = (inv * B) % MOD;
		X >>= 1;
		B = (B * B) % MOD;
	}

	cout << (A * inv) % MOD;
}