백준 16176번: Liar Game

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

16176번: Liar Game

---

지문의 해독이 정말 어려운 문제였습니다.

 

심지어 원래는 지문에 오류도 있었다는데...

 

일단, 정답을 구하기 위해서 Kanzaki Nao와 Fukunaga Yuuji 가 벌이는

 

"Light vs Dark" 게임을 어느정도는 읽어보겠습니다.

 

---

 

먼저 이 게임은 카드 여러 장이 들어있는 "Bag"에서 "Card"을 한 장 꺼냅니다.

 

현재 "Bag"에는 "Card"가 두 종류 있는데, "Light Card"는 한 쪽이 "Joker", 한 쪽은 "back"입니다.

 

그리고 다른 한 종류는 "Dark Card"인데, 이는 두 면이 모두 "back"입니다.

 

그러므로 "Bag"에서 "Card"을 한 장 꺼낼 경우의 수는 세 가지인데, 다음과 같습니다.

 

(1) "Light"을 꺼냈으나 "back"이 보이도록 뽑은 경우

 

(2) "Light"을 꺼냈으나 "Joker"이 보이도록 뽑은 경우

 

(3) "Dark"을 꺼낸 경우

 

이 세 가지 경우의 수에 대해, 점수의 변화는 다음과 같습니다.

 

먼저 (2)의 경우는 Nao와 Yuuji가 모두 점수를 얻지 못합니다. (원문: proceed to the next round. this round is lost)

 

그리고 (1)은 Nao에게 +1점, (3)은 Yuuji에게 +1점에 해당합니다.

 

마지막으로 뽑았던 카드를 다시 "Bag"에 넣는 걸로 하나의 round가 종료됩니다.

 

---

 

문제에서 물어보는 것은, 이러한 "Light vs Dark" 게임에서

 

"Bag"에 1장의 "Light" 카드와 $N-1$ 장의 "Dark" 카드가 있는 상황을 가정하면,

 

Nao가 정확히 $R$ rounds 뒤에 획득한 점수가 정확히 $K$ 점이 될 확률에 관한 수식의 값입니다.

 

지문에서는 이를 $P$ 라고 부르는데, 사실 $R$ 과 $K$ 값에 따른 $P$ 값의 점화식을 유도할 수는 있습니다.

 

이 글에서는 점화식을 간단하게 다뤄보고, 다른 방향에서의 접근을 논의하겠습니다.

 

---

 

점화식을 유도하기 위해, 다음과 같은 식을 정의하겠습니다.

 

$X \left ( R \; , \; K \right )$ : $R$ rounds 뒤에 Nao의 점수가 정확히 $K$ 일 확률

 

이렇게 정의하면 다음을 얻을 수 있습니다.

 

$$ X \left ( R \; , \; K \right ) = \left ( 1 - \frac{1}{2N} \right ) X \left ( R-1 \; , \; K \right ) + \left ( \frac{1}{2N} \right ) X \left ( R \; , \; K \right ) $$

 

$$ X \left ( K \; , \; K \right ) = \left ( \frac{1}{2N} \right ) ^{K} $$

 

$$ X \left ( x \; , \; 0 \right ) = \left ( 1 - \frac{1}{2N} \right ) ^{x} $$

 

이는 앞서 게임을 소개할 때 (1)의 사건이 일어날 확률이 $\frac{1}{2N}$ 이기 때문입니다.

 

하지만 이걸 풀기 위해 13182번이나, 13173번의 풀이를 떠올리는 것은 너무 손해입니다.

 

다른 방향으로 접근하겠습니다.

 

---

 

13182번과 이 문제의 차이는 무엇일까요?

 

13182번에서는 빨간 제비를 뽑을 때마다 빨간 제비의 개수가 변했습니다.

 

이 문제에서는 Light이든 Dark이든 뭘 뽑더라도 전체 Card의 개수는 일정합니다.

 

13173번과 이 문제의 차이는 무엇일까요?

 

이 문제에서는 총 $R$ rounds 라는 게임의 시행 횟수가 정해져있습니다.

 

13173번에서는 그 횟수가 명시적으로 정해져있진 않지요.

 

그래서 위와 같은 특징이 우리에게 주는 효과는 무엇일까요?

 

지문에서 말해주는 것과 같이 (원문: P is the probability of picking the face-down Joker K times)

 

결국 $R$ 번의 시행에서 $K$ 번 특정 사건이 일어날 확률이 우리가 찾는 것이 됩니다.

 

이는 곧 이항정리를 활용하여 다음 식으로 귀결됩니다.

 

$$ P = _{R}C_{K} \times \left ( \frac{1}{2N} \right )^{K} \times \left ( 1 - \frac{1}{2N} \right )^{R-K} $$

 

그러면 이 $P$ 는 우리가 앞서 구했던

 

$X \left ( R \; , \; K \right)$ 의 점화식과 매우 밀접한 관련이 있는 것도 알 수 있을 것입니다.

 

---

 

당연히 여기서 끝이 아닙니다.

 

문제에서 구해야 하는 값은 다음과 같습니다.

 

$$P \times \left ( 2N \right )^{R} \;\; \mod \;\; 1000003 $$

 

그렇다면, $P$ 을 적당히 페르마의 소정리 등을 이용하여 먼저 구해야 할까요?

 

$P$ 를 잘 변형해봅시다.

 

$$P \; = \; _{R}C_{K} \times \left ( \frac{1}{2N} \right )^{K} \times \left ( 1 - \frac{1}{2N} \right )^{R-K} $$

 

$$ = \; \left ( \frac{1}{2N} \right )^{R} \times _{R}C_{K} \times \left ( 2N-1 \right )^{R-K} $$

 

따라서 다음을 얻을 수 있습니다!

 

$$ P \times \left ( 2N \right )^{R} = _{R}C_{K} \times \left ( 2N-1 \right )^{R-K} $$

 

---

 

위 식의 형태는 페르마의 소정리를 이용하면 빠른 시간 안에 계산할 수 있습니다.

 

전처리를 아예 하지 않는다면 하나의 쿼리당 $_{R}C_{K}$ 의 계산에 $O \left ( R \log P \right )$ 정도가 예상됩니다.

 

그렇게 하면 $T$ 개의 쿼리가 들어올 때 $O \left ( TR \log P \log R \right )$ 이 될 것 같습니다.

 

다만, 이 문제에서 다루는 $R$ 의 범위가 충분히 작은 값이므로

 

전처리를 $O \left ( R \right )$ 에 해주면 $O \left ( T \log R \right )$ 에 쿼리를 처리할 수 있습니다.

 

이에 따라 제가 작성한 코드는 다음과 같습니다.

 

/*
 * Author : thdtjdals3
 * Date : 2021-12-18
 * Description : BOJ 16176
 * Link : https://www.acmicpc.net/problem/16176
 */

#include <stdio.h>
#include <stdlib.h>

#define mod 1000003

long long power_modular (long long A, long long X);

int main() {
	
	long long* fac = malloc(sizeof(long long) * 100001);
	long long* inv = malloc(sizeof(long long) * 100001);
	
	fac[0] = fac[1] = 1;
	for (long long i = 2; i <= 100000; i++)
	{
		fac[i] = fac[i-1] * i % mod;
	}
	
	inv[100000] = power_modular(fac[100000], mod - 2);
	for (long long i = 99999; i >= 0; i--)
	{
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
	
	int T;
	scanf("%d", &T);
	
	while(T--)
	{
		long long N, R, K;
		scanf("%lld %lld %lld", &N, &R, &K);

		long long rCk = fac[R];
		rCk = rCk * inv[K] % mod;
		rCk = rCk * inv[R - K] % mod;
		
		long long ans = power_modular(2*N - 1, R - K);
		ans = ans * rCk % mod;

		printf("%lld\n", ans);
	}
	return 0;
}

long long power_modular (long long A, long long X)
{
	long long result = 1;
	while(X)
	{
		if (X % 2)
		{
			result = result * A % mod;
		}
		A = A * A % mod;
		X /= 2;
	}
	return result;
}

(C11, 2684KB, 4ms, 제출번호 36420160)

---