結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | Mao-beta |
提出日時 | 2024-04-03 19:40:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 100 ms / 5,000 ms |
コード長 | 2,190 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 82,328 KB |
実行使用メモリ | 141,748 KB |
最終ジャッジ日時 | 2024-10-01 00:02:56 |
合計ジャッジ時間 | 4,070 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import sysimport mathimport bisectfrom heapq import heapify, heappop, heappushfrom collections import deque, defaultdict, Counterfrom functools import lru_cachefrom itertools import accumulate, combinations, permutations, productsys.setrecursionlimit(1000000)MOD = 10 ** 9 + 7MOD99 = 998244353input = lambda: sys.stdin.readline().strip()NI = lambda: int(input())NMI = lambda: map(int, input().split())NLI = lambda: list(NMI())SI = lambda: input()SMI = lambda: input().split()SLI = lambda: list(SMI())EI = lambda m: [NLI() for _ in range(m)]# 行列積(任意サイズ)def mul_matrix(A, B, mod=998244353):Ah = len(A)Aw = len(A[0])Bh = len(B)Bw = len(B[0])assert Aw == BhC = [[0] * Bw for _ in range(Ah)]for h in range(Ah):Arow = A[h]Crow = C[h]for i in range(Aw):a = Arow[i]Brow = B[i]for w in range(Bw):Crow[w] = (Crow[w] + a * Brow[w]) % modreturn C# 正方行列の累乗 moddef pow_matrix(A, n, mod=998244353):assert len(A) == len(A[0])bitn = len(bin(n)) - 2pows = []size = len(A)E = [[0] * size for _ in range(size)]for i in range(size):E[i][i] = 1pows.append(A)ans = Efor i in range(bitn):if (n >> i) & 1:ans = mul_matrix(pows[-1], ans, mod)pows.append(mul_matrix(pows[-1], pows[-1], mod))return ansdef main():N, K = NMI()A = NLI()if K <= 10**6:S = sum(A)for i in range(K-N):A.append(S % MOD)S = S - A[i] + A[i+N]print(A[-1], sum(A) % MOD)else:B = [[0]*(N+1) for _ in range(N+1)]B[0] = [1] * (N+1)B[0][-1] = 0for i in range(N-1):B[i+1][i] = 1B[-1] = [1] * (N+1)C = pow_matrix(B, K-N, MOD)A = A[::-1]A.append(sum(A))f, s = 0, 0for j in range(N+1):f += C[0][j] * A[j] % MODf %= MODfor j in range(N+1):s += C[-1][j] * A[j] % MODs %= MODprint(f, s)if __name__ == "__main__":main()