글 읽기 - 이거 O(log(n)) 아닌가요..?

johnkoh1107 2년 전 0

아무리 봐도 log(n)인데..

li=dict()
li[0]=2
li[1]=6
def ans(n):
    global li
    if n==1:
        
        return 6
    if n==0:
        return 2
    if n in li:
        return li[n]
    if n%2==0:
        li[n]=(ans(n//2)**2)-2*(4**(n//2))
        return li[n]
    li[n]=(ans(n//2)*ans(n//2 +1)-6*(4**(n//2)))
    return li[n]
for _ in range(int(input())):
    n=int(input())
    print('Case #', _+1, ': ', str((ans(n)-1)%1000).zfill(3), sep='')

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이거 O(log(n)) 아닌가요..?

johnkoh1107 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말