Ch 11. 수학 (Mathematics)

Lesson 211. 수학과 게임 이론

Mathematics & Game Theory: Modulo arithmetic, Combinatorics, Matrix, and Nim Game - 빠른 거듭제곱과 페르마 소정리의 지수 감축 - 팩토리얼 역원 전처리를 이용한 $O(1)$ 이항 계수 쿼리 - 행렬 거듭제곱을 활용한 초고속 피보나치 수 계산 - XOR 비트합(Nim-sum)을 통한 조합 게임 분석

수업 목표 및 핵심 역량

- 다중 거듭제곱 시 모듈러 법의 대수적 변화 규칙을 체득합니다. - 나눗셈의 모듈러 역원을 구하는 페르마 정리 및 $O(N)$ 선형 역원 확장을 구현합니다. - 선형 점화식 전이 관계를 행렬식으로 구조화하고 거듭제곱으로 단축합니다. - 공평 게임의 상태 전이를 XOR 합(Nim-sum)으로 추상화하여 필승 판단을 내립니다.

빠른 거듭제곱 II

- 지수부에 $p-1$ 모듈러를 적용한 빠른 거듭제곱 구현

# 8057번: 빠른 거듭제곱 II 발췌
# a^(b^c) mod p
exp = power(b, c, p - 1)
ans = power(a, exp, p)

이항 계수 쿼리 역원 전처리

- 역순 전파를 통해 단 $O(N)$에 모든 팩토리얼 역원 구축

# 8058번: 이항 계수 쿼리 발췌
inv_fact = [1] * (MAX + 1)
inv_fact[MAX] = power(fact[MAX], p - 2)
for i in range(MAX - 1, -1, -1):
    inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % p

행렬 거듭제곱 피보나치

- 행렬 거듭제곱 분할정복으로 $O(\log N)$에 피보나치 수 연산

# 8059번: 피보나치 수열 발췌
T = [[1, 1], [1, 0]]
res = power_matrix(T, n - 1, p)
fib_n = res[0][0]

님 게임 (Nim Game)

- 각 더미 크기의 XOR 합(Nim-sum)이 0이 아니면 선공 필승

# 8060번: 님 게임 발췌
xor_sum = 0
for num in x:
    xor_sum ^= num
winner = "first" if xor_sum != 0 else "second"

오류 예방 및 안정성 체크

- **지수 모듈러 혼동 차단**: 지수에는 $p$가 아닌 $p-1$이 법으로 들어감을 항시 인지 - **음수 보정 연산 준수**: 나눗셈 모듈러 차 연산 시 (A - B + p) % p 공식을 적극 활용해 음수 오버플로우 방지 - **N=0 경계치 보정**: 피보나치 수열 $N=0$ 입력 시 0을 가로채어 리턴하도록 안정적 예외 분기문 처리

ESC — 수업으로 돌아가기 · F — 전체화면