Submission #19081132


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 poly_coef(N, P, Q):
    while N:
        Qminus = [-Q[i]%MOD if i&1 else Q[i] for i in range(len(Q))]
        Q = convolve(Q, Qminus)[::2]
        P = convolve(P, Qminus)[N&1::2] 
        N >>= 1
    return P[0]

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

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

Submission Info

Submission Time
Task T - フィボナッチ
User Tallfall
Language PyPy3 (7.3.0)
Score 8
Code Size 873 Byte
Status AC
Exec Time 385 ms
Memory 82212 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 385 ms 82212 KB
01 AC 277 ms 76692 KB
02 AC 362 ms 82016 KB
03 AC 187 ms 70836 KB
04 AC 169 ms 74076 KB
90 AC 56 ms 62020 KB
91 AC 58 ms 62164 KB