Submission #19081073


Source Code Expand

Copy
import sys
readline = sys.stdin.readline


bsize = 71
#1<<bsize > N*max(A)*max(A)
block = 1<<bsize
MOD = 10**9+7
def convolve(A, B):
    L = len(A) + len(B) - 1
    iA = int(''.join([bin(block|a)[-bsize:] for a in A[::-1]]), 2)
    iB = int(''.join([bin(block|b)[-bsize:] for b in B[::-1]]), 2)
    stAB = format(iA*iB, 'b')
    C = [0]*L
    C[0] = int(stAB[-bsize:], 2)%MOD
    for i in range(1, L):
        c = stAB[-(i+1)*bsize:-i*bsize]
        if c:
            C[i] = int(c, 2)%MOD
    return C
def calc(N, P, Q):
    #[x^0]Q = 1
    #calculate [x^N]P/Q
    if not N:
        return P[0]
    Qminus = [-Q[i]%MOD if i&1 else Q[i] for i in range(len(Q))]
    QQm = convolve(Q, Qminus)
    QQm = [QQm[i] for i in range(len(QQm)) if not i&1] 
    PQm = convolve(P, Qminus) 
    if N&1:
        PQmodd = [PQm[i] for i in range(len(PQm)) if i&1]
        return calc(N//2, PQmodd, QQm)
    else:
        PQmeven = [PQm[i] for i in range(len(PQm)) if not i&1]
        return calc(N//2, PQmeven, QQm)

K, N = map(int, readline().split())

f = [1]*K
h = [1] + [MOD-1]*K
g = convolve(f, h)[:K]
print(calc(N-1, g, h)%MOD)

Submission Info

Submission Time
Task T - フィボナッチ
User Tallfall
Language PyPy3 (7.3.0)
Score 8
Code Size 1157 Byte
Status AC
Exec Time 397 ms
Memory 85244 KB

Judge Result

Set Name All
Score / Max Score 8 / 8
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 397 ms 85244 KB
01 AC 286 ms 78632 KB
02 AC 383 ms 84772 KB
03 AC 193 ms 72804 KB
04 AC 178 ms 75220 KB
90 AC 56 ms 62452 KB
91 AC 55 ms 62496 KB