結果
問題 |
No.1073 無限すごろく
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:25:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 1,196 bytes |
コンパイル時間 | 199 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 61,312 KB |
最終ジャッジ日時 | 2025-03-31 17:25:20 |
合計ジャッジ時間 | 2,775 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
MOD = 10**9 + 7 def multiply_matrix(a, b): res = [[0] * 6 for _ in range(6)] for i in range(6): for k in range(6): if a[i][k] == 0: continue for j in range(6): res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD return res def matrix_power(mat, power): result = [[0] * 6 for _ in range(6)] for i in range(6): result[i][i] = 1 # Identity matrix while power > 0: if power % 2 == 1: result = multiply_matrix(result, mat) mat = multiply_matrix(mat, mat) power //= 2 return result def create_transfer_matrix(): inv6 = pow(6, MOD - 2, MOD) mat = [[0 for _ in range(6)] for _ in range(6)] for i in range(6): mat[i][0] = inv6 for j in range(1, 6): mat[j-1][j] = 1 return mat def multiply_vector(v, mat): res = [0] * 6 for j in range(6): s = 0 for k in range(6): s = (s + v[k] * mat[k][j]) % MOD res[j] = s return res n = int(input()) transfer_mat = create_transfer_matrix() mat = matrix_power(transfer_mat, n) v = [1] + [0] * 5 res_v = multiply_vector(v, mat) print(res_v[0])