Submission #19684390


Source Code Expand

Copy
mod = 10**9 + 7
def mat_dot(a, b):
    n = len(a)
    r = len(a[0])
    m = len(b[0])
    c = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(r):
                c[i][j] += a[i][k] * b[k][j]
                c[i][j] % mod
    return c
def mat_pow(a, n):
    m = len(a)
    b = [[1 if i == j else 0 for j in range(m)] for i in range(m)]
    while n > 0:
        if n & 1:
            b = mat_dot(b, a)
        a = mat_dot(a, a)
        n >>= 1
    return b
k, n =  map(int, input().split())
if n <= k:
    print(1)
    exit()
a = [[1 if i == 0 or i - 1 == j else 0 for j in range(k)] for i in range(k)]
a = mat_pow(a, n - k)
a = mat_dot(a, [[1] for i in range(k)])
print(a[0][0])

Submission Info

Submission Time
Task T - フィボナッチ
User spring1105
Language Python (3.8.2)
Score 0
Code Size 776 Byte
Status TLE
Exec Time 2206 ms
Memory 35480 KB

Judge Result

Set Name All
Score / Max Score 0 / 8
Status
AC × 3
TLE × 4
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 TLE 2206 ms 35392 KB
01 TLE 2206 ms 25104 KB
02 TLE 2206 ms 35480 KB
03 TLE 2206 ms 12576 KB
04 AC 20 ms 9028 KB
90 AC 20 ms 8920 KB
91 AC 20 ms 9100 KB