문제 90

파이 쟁탈전

내 상태: 미제출
난이도: 90번 문제 난이도 보기

Gold III
출제자: pizzaroot
시간 제한: 1000 ms
메모리 제한: 512 MB

태그 보기

게임 이론모듈로 곱셈 역원수학정수론확률론

2023년 세종대학교에서는 "파이 쟁탈전"이 열렸다.

"이과는 ChatGPT 하위호환"이라는 문과의 도발을 본 이과는 너무나도 화가 나서 문과를 혼내주기 위해 게임을 준비했다.

바로 "배스킨라빈스 $N$ 게임"이다. 게임의 규칙은 다음과 같다.

두 명의 플레이어인 이과와 문과가 턴을 번갈아 가면서 게임을 진행하며, 이과가 먼저 시작한다.
각 턴에는 현재까지 불리지 않은 가장 작은 양의 정수부터 차례대로, $1$개 이상 $3$개 이하의 연속된 정수를 부른다.
$N$을 부르는 플레이어가 패배한다.

이 게임은 너무나도 유명해서 이과는 이 게임의 최선의 전략을 알고 있지만, 문과는 그러한 전략을 모른다.

따라서 이과는 자신의 턴마다, 문과가 어떤 선택을 하더라도 승리할 수 있는 전략이 존재한다면 그 전략에 따라 정수를 부르고, 그렇지 않다면 $1$개를 부른다.

반면에 문과는 자신의 턴마다 $1$개, $2$개, $3$개 중 하나를 동일한 확률로 선택하여 부른다.

정수 $N$이 주어졌을 때, 이과가 승리할 확률을 구해보자.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 10^9)$

출력

첫 번째 줄에 이과가 승리할 확률을 $998\,244\,353$으로 나눈 나머지를 출력한다. $998\,244\,353$은 소수이다.

구체적으로, 가능한 모든 입력에 대해 이과가 승리할 확률이 항상 유리수임을 보일 수 있으며, 이를 기약분수 $p/q$ $(p \ge 0; q>0)$로 나타냈을 때 $qx-p$가 $998\,244\,353$의 배수인 $0$ 이상 $998\,244\,353$ 미만의 정수 $x$가 항상 유일하게 존재한다. 이때, $x$를 출력해야 한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

665496236

공식 해설 풀이 스포일러 보기 접기

필패 상태는 남은 수가 $4$로 나눈 나머지 $1$인 경우이다

아직 부르지 않은 수가 $r$개 남았다고 하자. $r=1$이면 현재 차례의 사람이 반드시 패배한다. $r\equiv1\pmod4$에서 $1,2,3$개를 부르면 상대에게 나머지가 $1$이 아닌 상태를 주고, 그 밖의 상태에서는 적절한 개수를 불러 상대에게 나머지가 $1$인 상태를 줄 수 있다.

따라서 완벽하게 플레이할 때 $r\equiv1\pmod4$인 상태만 필패 상태이다. 처음 $N\not\equiv1\pmod4$이면 이과가 필승 전략을 쓰므로 답은 $1$이다.

필패 상태가 계속 이어질 확률

$N=4k+1$이라 하자. 이과는 한 개를 불러 문과에게 $4k$개가 남은 상태를 준다. 문과가 한 개나 두 개를 부르면 다음 이과 차례는 필승 상태가 된다. 이때부터는 문과의 선택과 관계없이 이과가 이긴다.

문과가 세 개를 부르면 이과에게 다시 $4(k-1)+1$개가 남는다. 따라서 이과가 끝까지 패배하려면 문과가 $k$번 연속 세 개를 골라야 한다. 그 확률은 $(1/3)^k$이므로 승리 확률은
\[ 1-3^{-k} \]
이다. $N=1$이면 $k=0$이므로 같은 식에서 $0$을 얻는다.

소수 $p=998\,244\,353$에 대한 $3$의 역원 $u=3^{p-2}\bmod p$를 구하고, 빠른 거듭제곱으로 $u^k\bmod p$를 계산한다. 답은 $(1-u^k)\bmod p$이며 음수인 나머지는 $p$를 더해 보정한다.

시간복잡도는 $O(1+\log N+\log p)$, 추가 공간복잡도는 $O(1)$이다.

구현 · 언어별 풀이

C++ 구현

$N$을 $4$로 나눈 나머지가 $1$이 아니면 $1$을 출력한다. 그 밖에는 $k=(N-1)/4$를 구해 빠른 거듭제곱을 수행한다. 곱은 long long으로 계산하고, 최종 나머지는 (1 - value + mod) % mod로 음수가 되지 않게 한다.

C 구현

N%4에 따라 먼저 답을 나누고 필요한 경우 (N-1)/4를 지수로 사용한다. 모듈러 곱은 long long이며 1-value의 나머지는 1+p-value로 양수화한다.

Python 구현

모듈러 역원과 지수 계산에 세 인수 pow를 쓴다. 마지막 (1-value)%p는 Python에서 0 이상 나머지를 준다. 3의 큰 거듭제곱이나 Fraction 객체를 만들지 않는다.

Java 구현

long으로 모듈러 거듭제곱을 구현한다. Java의 음수 %를 그대로 답으로 쓰지 말고 (1+p-value)%p로 정규화한다. N=1도 지수 0으로 처리된다.

Rust 구현

u64 모듈러 연산을 사용한다. 1-value를 먼저 계산하면 언더플로할 수 있으므로 (1+p-value)%p로 계산한다. 필요한 지수만 이진 거듭제곱한다.

JavaScript 구현

입력 $N$은 Number로 정확하지만 모듈러 곱은 안전 정수 범위를 넘는다. 나머지 분기는 작은 정수로 확인하고, 빠른 거듭제곱의 밑·결과·모듈러는 BigInt로 계산한다.

function pow(a, e, mod) {
    let r = 1n;
    while (e > 0n) {
        if (e % 2n) r = r * a % mod;
        a = a * a % mod;
        e /= 2n;
    }
    return r;
}
const p = 998244353n;
const inv3 = pow(3n, p - 2n, p);
const k = BigInt((n - 1) / 4);
console.log(((1n - pow(inv3, k, p) + p) % p).toString());

위 계산은 n % 4 === 1인 분기에 사용하고 다른 분기의 답은 $1$이다. JS의 음수 나머지를 보정하기 위해 마지막에 $p$를 더한다. $N=1$에서도 $k=0$이라 답 $0$을 얻는다. 거대한 $3^k$를 직접 만들지 않는다.

제출

언어