Submission #5022612
Source Code Expand
K, N = map(int, input().split()) P = 10**9+7 KK = 80 def ltoi(L): ret = 0 for i in range(len(L)): ret += L[i] << KK*i 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 Info
Submission Time | |
---|---|
Task | T - フィボナッチ |
User | Kiri8128 |
Language | PyPy3 (2.4.0) |
Score | 8 |
Code Size | 833 Byte |
Status | AC |
Exec Time | 561 ms |
Memory | 50012 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 8 / 8 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 561 ms | 50012 KB |
01 | AC | 384 ms | 45788 KB |
02 | AC | 540 ms | 49756 KB |
03 | AC | 254 ms | 42204 KB |
04 | AC | 204 ms | 41196 KB |
90 | AC | 170 ms | 38256 KB |
91 | AC | 161 ms | 38256 KB |