Typical DP Contest

Submission #5410498

Source codeソースコード

K, N = map(int, input().split())
P = 10**9+7

KK = 70
def ltoi(L):
    ret = 0
    for l in L[::-1]:
        ret <<= KK
        ret += l
    return ret
def itol(n):
    ret = []
    for i in range(2*K-1):
        ret.append((n>>i*KK) & ((1<<KK)-1))
    return ret

def mult(A, B):
    return itol(ltoi(A)*ltoi(B))
def prod(A, B):
    C = mult(A, B)
    for i in range(len(C)):
        C[i] %= P
    for i in range(K+1, 2*K-1)[::-1]:
        C[i-1] += 2*C[i]
        C[i-K-1] -= C[i]
        C[i-1] %= P
        C[i-K-1] %= P
        C[i] = 0
    for i in range(K):
        C[i] += C[K]
        C[i] %= P
    C[K] = 0
        
    return C[:K]
def poww(A, n):
    if n == 1: return A
    if n % 2 == 0: return poww(prod(A,A), n//2)
    return prod(A, poww(A, n-1))

print(sum(poww([0,1], N-1))%P)

Submission

Task問題 T - フィボナッチ
User nameユーザ名 Kiri8128
Created time投稿日時
Language言語 PyPy3 (2.4.0)
Status状態 AC
Score得点 8
Source lengthソースコード長 836 Byte
File nameファイル名
Exec time実行時間 672 ms
Memory usageメモリ使用量 51164 KB

Test case

Set

Set name Score得点 / Max score Cases
All 8 / 8 00,01,02,03,04,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 672 ms 51164 KB
01 AC 429 ms 45148 KB
02 AC 617 ms 48732 KB
03 AC 265 ms 42076 KB
04 AC 189 ms 41196 KB
90 AC 163 ms 38256 KB
91 AC 165 ms 38256 KB