結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 21:45:36 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 1,300 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-12-17 14:05:39 |
合計ジャッジ時間 | 2,162 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sys readline = sys.stdin.readline ns = lambda: readline().rstrip() ni = lambda: int(readline().rstrip()) nm = lambda: map(int, readline().split()) nl = lambda: list(map(int, readline().split())) def Kitamasa(C, X, k, e0=0, e1=1, mod=10**9+7): ''' 0-indexed calc X[k] ''' n = len(X) def _plus1(g): ret = [(g[i-1] + g[-1] * C[i]) % mod for i in range(n)] ret[0] = g[-1] * C[0] % mod return ret def _mult2(g): ret = [e0]*(2 * n - 1) for i in range(n): for j in range(n): ret[i + j] = (ret[i + j] + g[i] * g[j]) % mod for i in range(2*n-2, n-1, -1): for j in range(n): ret[i + j - n] = (ret[i + j - n] + ret[i] * C[j]) % mod return ret[:n] g = [e0]*n g[0] = e1 t = k.bit_length() for i in range(t-1, -1, -1): g = _mult2(g) if k & (1<<i): g = _plus1(g) ans = e0 for i in range(n): ans = (ans + g[i] * X[i]) % mod return ans def modinv(x, mod): a, b = x, mod u, v = 1, 0 while b: t = a // b a -= t * b; a, b = b, a u -= t * v; u, v = v, u return u % mod def solve(): n = ni() mod = 10**9 + 7 inv6 = modinv(6, mod) X = [1, 166666668, 194444446, 893518525, 209104940, 577289099] C = [inv6]*6 print(Kitamasa(C, X, n)) return solve()