結果
問題 | No.2122 黄金比で擬似乱数生成 |
ユーザー |
👑 |
提出日時 | 2022-11-04 23:41:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,369 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 81,892 KB |
最終ジャッジ日時 | 2024-07-18 21:26:31 |
合計ジャッジ時間 | 8,091 ms |
ジャッジサーバーID (参考情報) |
judge5 / 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):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(2, 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 and m <= 35:nex[1] -= 1if nex[1] == -1:nex[1] = 9999n = int(S)doubling = [[-1] * 10000 for _ in range(60)]for i in range(10000):doubling[0][i] = nex[i]for i in range(1, 60):for j in range(10000):doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]for i in range(60):if L >> i & 1:n = doubling[i][n]ans = str(n).zfill(4)print(ans)