結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 22:10:43 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,343 bytes |
コンパイル時間 | 312 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-12-17 15:38:11 |
合計ジャッジ時間 | 2,072 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
mod = int(1e9) + 7vec = [1, 1, 7, 49, 343, 2401]for i in range(6):vec[i] *= 6**(5-i)def doubling(n, m):y = 1base = ntmp = mwhile tmp != 0:if tmp % 2 == 1:y *= basey %= modbase *= basebase %= modtmp //= 2return ydef inved(a):x, y, u, v, k, l = 1, 0, 0, 1, a, modwhile l != 0:x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)k, l = l, k % lreturn x % moddef matprod(m1, m2, n, l, m):y = [[0 for _ in range(m)] for __ in range(n)]for i in range(n):for j in range(m):for k in range(l):y[i][j] += m1[i][k] * m2[k][j] % mody[i][j] %= modreturn ydef matpow(m1, n, m):y = [[i==j for j in range(n)] for i in range(n)]bas = [[m1[i][j] for j in range(n)] for i in range(n)]tmp = mwhile tmp != 0:if tmp % 2 == 1:y = matprod(y, bas, n, n, n)[:][:]bas = matprod(bas, bas, n, n, n)[:][:]tmp //= 2return yN = int(input())bas = [[0 for j in range(6)] for i in range(6)]for i in range(5):bas[i][i+1] = 6bas[-1][i] = 1bas[-1][-1] = 1mat = matpow(bas, 6, N)S = 0for i in range(6):S += vec[i] * mat[0][i] % modS %= modprint(S*inved(doubling(6, N+5))%mod)