結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 21:36:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 927 bytes |
コンパイル時間 | 416 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 62,172 KB |
最終ジャッジ日時 | 2024-12-17 13:42:50 |
合計ジャッジ時間 | 2,584 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sysreadline = sys.stdin.readlinedef mat_dot(A, B, mod):assert len(A[0]) == len(B), 'invalid_size'L = len(A)M = len(A[0])N = len(B[0])res = [[0]*N for _ in range(L)]for i in range(L):for j in range(N):a = 0for k in range(M):a = (a+A[i][k]*B[k][j]) % modres[i][j] = areturn resdef mat_pow(A, x, mod):N = len(A)res = [[0]*N for _ in range(N)]for i in range(N):res[i][i] = 1for i in range(x.bit_length()):if 2**i & x:res = mat_dot(res, A, mod)A = mat_dot(A, A, mod)return resMOD = 10**9+7N = int(readline())init = [[0] for _ in range(6)]init[0][0] = 1sinv = pow(6, MOD-2, MOD)Mat = [[sinv]*6] + [[0]*6 for _ in range(5)]for i in range(1, 6):Mat[i][i-1] = 1print(mat_dot(mat_pow(Mat, N, MOD), init, MOD)[0][0])