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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


본인은 파이썬으로 PS하는데, 알법한 애들은 다들 알다 싶이 PyRival이라고 유명한 파이썬 용 PS 라이브러리가 있음.

난 이걸 적극적으로 활용하고 고쳐서 잘 써먹고 있는데, 가끔 날먹급이다 싶은 문제들은 좀 공부가 안되는 것 같아서 풀이를 일부러 자세히 적으려고 함.


이 문제가 딱 그런류였음. 템플릿에 있는 make_nCr_mod 긁어다가 쓰면 딱 풀리는 문제인걸 되게 옛날부터 알고 있었어서

풀이 쓰기가 귀찮으니 안 풀고 미루다가 아까 풀어냈는데, 풀이도 재미가 없어서 시간복잡도를 분석했더니 생각보다 인사이트가 많아서 글 적음.


def gnCr(max_n, mod=10**9 + 7):
max_n = min(max_n, mod - 1)

fact, inv_fact = [0] * (max_n + 1), [0] * (max_n + 1)
fact[0] = 1
for i in range(max_n):
fact[i + 1] = fact[i] * (i + 1) % mod

inv_fact[-1] = pow(fact[-1], mod - 2, mod)
for i in reversed(range(max_n)):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

def nCr(n, r):
if n < r: return 0
res = 1
while n or r:
a, b = n % mod, r % mod
if a < b: return 0
res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
n //= mod
r //= mod
return res

return nCr


일단 내가 썼던 템플릿(원본이랑 좀 다름)

그리고 아래가 풀이임



katex 렌더링 때문에 이미지인거 ㅈㅅ


풀이는 넘기고, 시간복잡도를 구해보기로 함.

처음에 구해본 시간복잡도 식이 O(X + M(max(log_p n, log_p k))) 였는데,

이게 계속 수식을 보면 볼수록 개선점이 보이고,

결과적으로 수식이 간결해지는게 재밌어서 그 과정을 다 적어놨음 ㅋㅋㅋ

이게 진짜 수학 태그 달린 문제의 재미다 싶더라.


솔직히 지금도 너무 간결해서, 틀린거 아닌가 싶기도 함... 고수분들 지적해주면 ㄳ


어쨌든 클래스 밀다가 수학문제 보이면 한번 시간복잡도까지 쭉 구해보는것도 의미 있는거 같음.

PS 개꿀잼