108822024-04-17 18:12:5842Toronyépítés (80 pont)python3Elfogadva 80/8017ms13528 KiB
from sys import stdin
input=stdin.readline

mod=20210108

d={0:1,1:3,2:10,3:33,4:109,5:360}

def f(n):
    if n in d:
        return d[n]
    if n%2==0:
        cur=(f(n//2)**2+f(n//2-1)**2)%mod
        d[n]=cur
        return cur
    # n%2==1
    cur=(f(n//2)*(f(n//2-1)+f(n//2+1)))%mod
    d[n]=cur
    return cur

N=int(input())
print(f(N))
RészfeladatÖsszpontTesztVerdiktIdőMemória
base80/80
1Elfogadva0/017ms11064 KiB
2Elfogadva0/017ms11484 KiB
3Elfogadva4/417ms11612 KiB
4Elfogadva4/417ms12028 KiB
5Elfogadva5/517ms12332 KiB
6Elfogadva5/517ms12652 KiB
7Elfogadva6/617ms12424 KiB
8Elfogadva6/617ms12808 KiB
9Elfogadva7/717ms12744 KiB
10Elfogadva7/717ms12916 KiB
11Elfogadva8/817ms13156 KiB
12Elfogadva8/817ms13412 KiB
13Elfogadva8/817ms13216 KiB
14Elfogadva8/817ms13480 KiB
15Elfogadva2/217ms13528 KiB
16Elfogadva2/217ms13488 KiB