[일반] 오늘 백준 오픈콘 F어케품?

[익명(182.231)]

min( nCr, INT64_MAX )를 빠르게 구해야 한다는 결론밖에 안나오는데 O(n)에 구하자니 O(n^2)으로 시간초과 나고

어케품?

[대학원오지마세요(publfl)]

그거 나도 오버플로우 억까 무진장 당하고 걍 던짐 ㅅㅂ

[익명(116.37)]

nCk (k <= n - k 라 가정) k가 0 ~ 9 정도일 때만 팩토리얼로 직접 구하고, DP[1000][1000]정도만 잡음. 이제 앞에서 처리한 범위에서 벗어나는 수는 10^18 초과임 (예를들면 1000C10은 약 10^23). 파이썬은 쉽게 구현할텐데, 나는 그냥 __int128 쓰고 조건문 잘 써서 오버플로우 안나게 했음...