백준 13173번: Ω

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

13173번: Ω

---

문제를 관찰하면, 뭔가 복잡한 확률을 구해야 할 것 같습니다.

 

그리고, 출력 파트를 보면, 약분을 하여 분모가 1이 되지 않으면 $a\times b^{-1}$ 을 출력하라고 합니다.

 

중요한 건, 사실 약분 안 해도 됩니다.

 

$a\times b^{-1}=a\times \left ( 2\times 2^{-1} \right ) \times b^{-1}=\cdots$

 

위와 같이 생각하면 결국 약분은 문제가 아니죠.

---

 

이제 확률을 구하는 파트로 가면, 적당한 $P$, $Q$, $N$, $K$ 값에 대해 계속 사고실험을 해 봐야겠습니다.

 

$\left ( 1 \right )$ 숫자 $K$ 를 갖고 있습니다.

 

$\frac{Q}{P}$ 확률로 $K-1$ 로 떨어지거나, $\left ( 1-\frac{Q}{P} \right )$ 확률로 $K+1$ 로 올라갑니다.

 

$\left ( 2 \right )$ 숫자 $K+1$ 또는 $K-1$ 을 갖고 있습니다.

 

어떤 확률로 $K-2$, $K$, $K+2$ 가 될 수 있습니다.

 

이렇게 계속 이어나갈 순 없을 것 같아요.

 

일단 확률에 관한 수열을 예쁘게 정의해볼게요.

 

$\left \{ p_{i} \right \}$ : 숫자 $i$ 를 갖고 있는 상태에서

                      충분히 주사위를 굴려 게임이 끝난 뒤

$N$ 을 갖고 있을 확률

 

물론, $0$ 을 가질 확률로 정의해도 이후 과정에서 잘 풀어나가면

 

문제를 풀기에는 충분할 것 같습니다.

 

이제 이 수열의 점화 관계가 어떻게 되는지 살펴봅시다.

 

우선, 숫자 $i$ 를 가진 상태에서 $\frac{Q}{P}$ 확률로 $i-1$ 로 떨어지죠.

 

그러니까 $p_{i}$ 에는 $\frac{Q}{P}\times p_{i-1}$ 가 들어가있을 겁니다.

 

또 다른 경우는 $\left ( 1-\frac{Q}{P} \right )$ 확률로 $i+1$ 로 올라가는 경우입니다.

 

그러면 $p_{i}$ 에는 $\left( 1-\frac{Q}{P} \right)\times p_{i+1}$ 이 들어가 있겠네요.

 

결론적으로 점화식이 다음과 같이 나옵니다.

 

$p_{i}=\frac{Q}{P}\times p_{i-1}+\left( 1-\frac{Q}{P} \right)\times p_{i+1}$

 

이제 위 점화식의 제한 조건을 알아야 합니다. ( $i$ 의 범위 )

 

우선, 극단적인 값들을 알아야 하니까, $i=0$ 일 때를 생각해봅니다.

 

$i=0$ 이 된 순간 게임은 끝나고, $N$ 을 가질 수 없으니 확률은 0이 됩니다. $\left ( p_{0}=0 \right)$

 

반대로 $i>0$ 이면 점화식을 만족한다고 할 수 있겠네요.

 

점화식 속 $i$ 의 상한을 알기 위해 $i=N$ 을 가정합니다.

 

$i=N$ 인 순간 게임은 끝나고, 항상 $N$ 을 가진 상태이므로 확률은 1입니다. $\left ( p_{N}=1 \right)$

 

따라서, 점화식을 만족하는 $i$ 의 범위는 $0<i<N$ 이었습니다! $\cdots$ 주어진 초기값은 겨우 2개이고요.

 

그래서 각각의 값을 구하자니, 지나치게 오래 걸립니다.

 

솔루션 원본에서는 gaussian elimination 을 제안하기도 하네요.

 

애초에 솔루션에서도 진지하게 gaussian elimination을 사용한 코드를 제시 안 하고...

 

(0802) gaussian elimination으로 밀어버린 분이 계시네요. 

 

---

 

아무튼 이제 점화식을 통해 일반항을 구합니다.

 

우선 식의 가독성을 위해 다음 변수를 도입합니다.

 

 

$u=\frac{Q}{P}$

$p_{i}=u\times p_{i-1}+\left(1-u\right)\times p_{i+1}$

 

 

이제 점화식을 이렇게 변형합니다.

 

 

$p_{i+1}=\frac{1}{1-u}p_{i}-\frac{u}{1-u}p_{i-1}$

 

 

이 점화식을 좋은 모양새로 바꿔주기 위해, $x$ 를 도입하여 다음처럼 써보겠습니다.

 

 

$p_{i+1}-x\;p_{i}=\left ( \frac{1}{1-u}-x \right )\left ( p_{i}-x\;p_{i-1} \right )$

 

 

원래 식과 비교하면 $x$ 에 관한 방정식이 등장합니다.

 

 

$\left ( \frac{1}{1-u}-x \right )\;x=\frac{-u}{1-u}$

 

$\leftrightarrow \left( 1-u \right)x^{2}-x+u=0$

 

$\leftrightarrow$ $x = \frac{u}{1-u}\;$ 또는 $\;x = 1$

 

 

이렇게 얻은 $x$ 값을 각각 대입해보면 다음을 얻습니다.

 

 

$\begin{cases} p_{i+1}-\frac{u}{1-u}p_{i}=p_{i}-\frac{u}{1-u}p_{i-1} & \text { if }\; x\;=\;\frac{u}{1-u} \\ \\ p_{i+1}-p_{i}=p_{i}-p_{i-1} & \text { if }\; x\;=\;1 \end{cases}$

 

 

따라서 아래 식을 얻을 수 있습니다.

 

 

$\left( \frac{u}{1-u}-1 \right)p_{i}=p_{1}-\left( \frac{u}{1-u} \right)^{i}p_{1}$

 

 

그러니까, 적절한 상수 $A$ , $B$ 를 도입하면 다음과 같이 일반항을 나타낼 수 있다는 뜻입니다.

 

$p_{i}=A+B\times \left( \frac{u}{1-u} \right)^{i}$

 

이 일반항은 당연히 $0\leq i\leq N$ 의 모든 $i$ 에 대해 만족되어야 합니다.

 

가독성을 위해 이제 $v=\frac{u}{1-u}$ 라 하면 다음 두 식을 얻습니다.

 

$\begin{cases} p_{0}=A+B=0 \\ \\ p_{N}=A+B\times v^{N}=1 \end{cases}$

 

두 식을 연립하면 $A$ , $B$ 의 값이 결정됩니다.

 

$A=\frac{-1}{v^{N}-1}$

$B=\frac{1}{v^{N}-1}$

 

이 말은 즉, 우리가 원했던 $p_{i}$ 가 다음과 같다는 것이죠.

 

$p_{i}=\frac{v^{i}-1}{v^{N}-1}$

 

 

앞서 언급했듯이, 이 $p_{i}$ 를 약분할 필요는 전혀 없습니다.

 

그래서, $p_{i}$ 를 구할 때 필요한 것은 다음 두 가지입니다.

 

$\left ( 1 \right )$ $v^{i}-1\;\; mod\; \left( 10^{9}+7 \right)$

 

$\left ( 2 \right )$ $\left( v^{N}-1 \right)^{-1}\;\; mod\; \left( 10^{9}+7 \right)$

 

아시다시피, 이를 구하기 위한 전제조건은 바로 $v$ 의 modulo $\left( 10^{9}+7 \right)$ 값입니다.

 

이를 어떻게 구할 수 있을까요?

 

$v$ 의 정의에서부터 다시 $v$ 를 $P$, $Q$ 에 관한 식으로 환원시키겠습니다.

 

$v=\frac{u}{1-u}=\frac{\frac{Q}{P}}{1-\frac{Q}{P}}=\frac{Q}{P-Q}$

 

$p_{i}$ 를 약분할 필요가 없었듯이, 마찬가지로 $v$ 를 구할 때도 약분할 필요가 없습니다!

 

이제 이를 구현하면 문제가 70% 정도 해결되는 것 같습니다.

---

이제 다양한 예외 처리를 해주어야 합니다.

 

일단, 조금 전의 부분에서 저희가 풀었던 방정식이 이와 같습니다.

 

$\left( 1-u \right)x^{2}-x+u=0$

 

 

만약 $u=1$ 이면 어떡하죠? 그런 케이스도 물론 해결해야 하지만,

 

그에 앞서 이차방정식이 중근을 갖는 경우를 생각해 볼 수 있습니다!

 

중근이라는 건 두 해가 같은 값을 갖는 경우니까, 단순히 이런 케이스입니다. (판별식을 써도 좋습니다)

 

$\frac{u}{1-u}=1\;\;\leftrightarrow\;\;u=\frac{1}{2}$

 

그러면, 이런 $u$ 의 값이 점화식을 어떻게 바꾸는 지 살펴봅시다.

 

$p_{i}=u\times p_{i-1}+\left(1-u\right)\times p_{i+1}=\frac{1}{2}p_{i-1}+\frac{1}{2}p_{i+1}$

 

$\leftrightarrow \;\; p_{i+1}-p_{i}=p_{i}-p_{i-1}$

 

놀랍게도 등차수열의 점화식이 되었습니다!

 

그렇다면 이 경우에도 항상 성립하는 초기값, $p_{0}=0$ 과 $p_{N}=1$ 을 생각하면, 일반항이 다음과 같겠군요.

 

$p_{i}=\frac{i}{N}$

 

물론 이 경우에도 분수를 약분할 필요가 전혀 없습니다.

 

그대로 구현하면 됩니다.

 

조건을 되짚어보면, $u=\frac{1}{2}$ , 즉 $P=2Q$ 일 때 이 답을 도출해내면 됩니다.

---

이제 조금 전에 넘어갔던 케이스를 다시 불러오겠습니다.

 

$u=1$ , 즉 $P=Q$ 인 케이스입니다.

 

그런데 $0\leq Q\leq P$ 를 고려하면 이는 꽤 극단적인 값입니다.

 

이 타이밍에 나머지 극단적인 값들도 다 고려해보겠다는 뜻입니다.

 

우선 $Q=P$ 인 경우, 주사위를 굴리는 족족 숫자가 떨어집니다. 그래서 항상 0으로 끝날 것 같습니다.

 

또한 $Q=0$ 인 경우, 주사위를 굴리는 족족 숫자가 올라갑니다. 그래서 항상 $N$ 으로 끝날 것 같습니다.

 

과연 그럴까요?

 

$Q=0$ 이라도 $K=0$ 이면 구하는 확률은 반드시 0입니다.

 

$Q=P$ 이라도 $K=N$ 이면 구하는 확률은 반드시 1입니다.

 

그래서, 예외 처리의 우선 순위는 $N$ 과 $K$ 임을 알 수 있습니다.

 

한편, $K$ 의 값은 어떤가요?

 

$K=0$ 이면 $P$ , $Q$ , $N$ 의 값 모두에 상관 없이 확률이 0입니다.

 

$K=N$ 이면 $P$ , $Q$ , $N$ 의 값 모두에 상관 없이 확률이 1입니다.

 

이는 여기까지 따라오신 분들이라면 쉽게 알 수 있을 것 같습니다.

---

이 모든 사항을 고려하여 코드를 구현하면 AC를 받을 수 있습니다.

 

$p_{K}$ 를 구하는 코드임을 주의하세요. 제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007

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

int main() {
	
	long long P, Q, N, K;
	scanf("%lld", &P);
	scanf("%lld", &Q);
	scanf("%lld", &N);
	scanf("%lld", &K);
	
	if (K == N) {
		printf("1");
		return 0;
	}
	if (K == 0) {
		printf("0");
		return 0;
	}
	if (P == Q) {
		printf("0");
		return 0;
	}
	if (Q == 0) {
		printf("1");
		return 0;
	}
	
	if (P == 2 * Q) {
		
		long long answer = K * power_modular(N, mod - 2) % mod;
		
		printf("%lld", answer);
		return 0;
	}
	
	long long temp = Q * power_modular(P, mod - 2) % mod;
	temp = temp * power_modular(1 - temp + mod, mod - 2) % mod;
	
	long long over = 1 - power_modular(temp, K) + mod;
	long long under = 1 - power_modular(temp, N) + mod;
	
	long long answer = over * power_modular(under, mod - 2) % mod;
	printf("%lld", answer);

	return 0;
}

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

(C11, 1116KB, 0ms, 제출번호 31542986)

---

원본 솔루션의 풀이에서 생략된 부분을 조금 더 늘여 썼습니다.

 

원래 어려워하는 조합론에다 이런 생소한 점화식 풀이가 합쳐지니 저에겐 매우 어려운 문제였습니다.

 

우선순위 말인데요, 말은 안 했지만 $P\;,\;Q$ 조건과 $K\;,\;N$ 조건의 우선순위는 같습니다.