109282024-04-19 19:59:3242Toronyépítés (1,1,3,3)python3Accepted 50/5018ms13396 KiB
memo={0:1,1:2,2:4,3:10,4:24,5:56}

def t(n):
    if n in memo:
        return memo[n]
    if n%2==0:
        cur=(t(n//2-1)*t(n//2+1)+2*(t(n//2-3)*t(n//2)+t(n//2-2)*t(n//2-1)))%20210108
        memo[n]=cur
        return cur
    # n%2==1
    cur=(t(n//2)*t(n//2+1)+2*(t(n//2-2)*t(n//2)+t(n//2-1)*t(n//2-1)))%20210108
    memo[n]=cur
    return cur

print(t(int(input())))
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/017ms11268 KiB
2Accepted0/018ms11644 KiB
3Accepted3/317ms11968 KiB
4Accepted3/317ms12104 KiB
5Accepted4/417ms12232 KiB
6Accepted4/417ms12528 KiB
7Accepted4/417ms12476 KiB
8Accepted4/417ms12588 KiB
9Accepted4/417ms12736 KiB
10Accepted4/418ms12620 KiB
11Accepted4/417ms12660 KiB
12Accepted4/417ms12784 KiB
13Accepted4/417ms12976 KiB
14Accepted4/417ms13016 KiB
15Accepted2/217ms13384 KiB
16Accepted2/217ms13396 KiB