結果
問題 | No.2122 黄金比で擬似乱数生成 |
ユーザー |
👑 |
提出日時 | 2022-11-04 23:29:02 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,339 bytes |
コンパイル時間 | 236 ms |
コンパイル使用メモリ | 82,196 KB |
実行使用メモリ | 79,024 KB |
最終ジャッジ日時 | 2024-07-18 21:18:03 |
合計ジャッジ時間 | 6,952 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 WA * 2 |
ソースコード
"""S = 0001の遷移 わかってない"""MOD = 10000def add(x, y):if x[0] == 0:return yelif y[0] == 0:return xx = list(x)y = list(y)if x[1] > y[1]:x, y = y, xy[0] <<= y[1] - x[1]z0 = x[0] + y[0]z1 = x[1]return f(z0, z1)def times(x, y):x = list(x)y = list(y)z0 = x[0] * y[0]z1 = x[1] + y[1]return f(z0, z1)def matpow(A, B, w):l = len(A)while w:if w & 1:C = [(0, 0)] * lfor i in range(l):for j in range(l):C[i] = add(C[i], times(A[i][j], B[j]))B = CC = [[(0, 0)] * l for _ in range(l)]for i in range(l):for j in range(l):for k in range(l):C[i][j] = add(C[i][j], times(A[i][k], A[k][j]))A = Cw >>= 1return Bdef matpow_normal(A, B, w):l = len(A)while w:if w & 1:C = [0] * lfor i in range(l):for j in range(l):C[i] += A[i][j] * B[j]C[i] %= MODB = CC = [[0] * l for _ in range(l)]for i in range(l):for j in range(l):for k in range(l):C[i][j] += A[i][k] * A[k][j]C[i][j] %= MODA = Cw >>= 1return BS = int(input())m = int(input())L = int(input())nex = [0] * 10000def f(x, r=0):if x == 0:return 0, 0while x % 2 == 0:r += 1x //= 2return x % MOD, rfor n in range(1, 10000):d = n * n + 4B = [f(2), f(0)]A = [[f(n, -1), f(d, -1)], [f(1, -1), f(n, -1)]]ret = matpow(A, B, m)ret = ret[1]nex[n] = ret[0] * pow(2, ret[1], MOD) % MODif m % 2 == 1:nex[n] -= 1if nex[n] == -1:nex[n] = 9999A = [[1, 1], [1, 0]]B = [0, 1]nex[1] = matpow_normal(A, B, m)[0]if m % 2 == 1:nex[1] -= 1if nex[1] == -1:nex[1] = 9999n = int(S)se = set()lst = []while n not in se:se.add(n)lst.append(n)n = nex[n]if len(lst) >= L + 1:ans = str(lst[L]).zfill(4)print(ans)exit()ii = lst.index(n)L -= iilst = lst[ii:]L %= len(lst)ans = str(lst[L]).zfill(4)print(ans)