2026-02-24 문제풀이

선물게임

풀이

먼저 피씨는 생각하지말고 수아만 생각해보자.

• 모두 한번에 성공할 확률 : $(\frac{1}{N})^M$
• 한 번 실패 후 성공할 확률 : $(\frac{1}{N})^{M-1}(\frac{N-1}{N})\left(\frac{1}{N-1}\right)= (\frac{1}{N})^M$
• 두 번 실패 후 성공할 확률 : $(\frac{1}{N})^M$ 모두 결국에 성공할 확률은 같다. 따라서 피씨가 수아 전에 성공하지만 않으면 된다.

수아가 모두 성공하면 애초에 피씨는 아무것도 안한다. 수아가 한 번 실패했다면 피씨가 모두 성공하지 않으면 된다. -> 피씨가 모두 성공할 확률은 $p_{0}=\frac{1}{N-1}(\frac{1}{N})^{M-1}$ 이다. -> 따라서 여사건으로 $1 - p_0$ 를 이용할 수 있다.

수아가 두 번 실패했다면 피씨는 한번안에 성공하면 안된다. 두 번 실패했다는건 피씨는 한 번 실패했다는 걸 뜻한다.

근데 이렇게 생각해보니까 위의 풀이는 틀린 것 같고 이건 굉장히 공정한 게임이라는 생각이 들었다. 이런 공개된 게임에서 최적으로 플레이하면 확률은 둘이 나눠가지게 된다. 서로 이길 확률은 $\frac{1}{2}$ 인 것 같았다.

그래서 한 줄씩 생각해보니 N이 홀수면 $\frac{\lceil{N/2}\rceil}{N}$ , 짝수면 $\frac{1}{2}$ 로 수아가 이긴다. 그리고 한 줄만 의미가 있는게 어짜피 맞추면 턴이 계속되고 상대가 맞춰서 간 수를 따라가면 되니까 이건 한 줄만 의미가 있다. 라고 생각했지만 틀렸다 ㅋㅋ

짝수면 1/2 그게 맞는 말이다. 하지만 홀수면 말이 다르다. 왜냐면 순서가 바뀔 수 있기 때문이다.
N이 홀수일 때를 생각해보자.

수아가 이길 확률 $p=\frac{\lceil{N/2}\rceil}{N}$,
피씨가 이길 확률 $q=\frac{\lfloor{N/2}\rfloor}{N}$
$dp[i]$ : i번째 열까지 완료했을 때, 수아가 이기고있는(턴을 유지하고 있는) 확률이라고 하면
점화식: \(dp[k] = p \times dp[k-1] + q \times (1 - dp[k-1])\)
위와 같은 점화식이 나온다. 이 점화식을 정리하면
\(dp[k] - \frac{1}{2} = \frac{1}{N}(dp[k-1] - \frac{1}{2})\)
따라서 $dp[M]$은
\(dp[M]=\frac{1}{2} + \frac{1}{2N^M} = \frac{N^M + 1}{2N^M}\)
이렇게 된다.

답을 구하면 되는데 N이 짝수니까 둘이 약분이 된다. 따라서 약분을 한 값을 mod 하면 된다. 위에를 $2\times 1e7$ 로 나누고 그 값을 이용해 다시 mod 해줬다. 아래는 $N^M$ 만 구하면 된다.

코드

N, M = map(int, input().split())
if N & 1 :
    mod = int(1E9)
    a = pow(N, M, 2*mod)
    p = ((a + 1) // 2) % mod
    q = a % mod
    print(p, q)
else : 
    print(1, 2)