結果
問題 |
No.2122 黄金比で擬似乱数生成
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:48:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 1,994 bytes |
コンパイル時間 | 271 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 54,348 KB |
最終ジャッジ日時 | 2025-04-16 15:48:47 |
合計ジャッジ時間 | 2,288 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
def matrix_mult(a, b, mod): return [ [ (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod, (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod ], [ (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod, (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod ] ] def matrix_pow(mat, power, mod): result = [[1, 0], [0, 1]] # Identity matrix while power > 0: if power % 2 == 1: result = matrix_mult(result, mat, mod) mat = matrix_mult(mat, mat, mod) power = power // 2 return result def compute_K_mod(n, M, mod): if M == 0: return 0 % mod elif M == 1: return 1 % mod matrix = [[n % mod, 1], [1, 0]] mat_pow = matrix_pow(matrix, M - 1, mod) K = (mat_pow[0][0] * 1 + mat_pow[0][1] * 0) % mod return K def apply_shuffle(current_n, M): mod = 10000 if current_n == 0: if M % 2 == 0: K_M = 0 else: K_M = 1 s = K_M new_n = (K_M - s) % mod else: K_M = compute_K_mod(current_n, M, mod) s = 1 if M % 2 == 1 else 0 new_n = (K_M - s) % mod return new_n def solve(): S = input().strip() M = int(input()) L = int(input()) current_n = int(S) memo = {} path = [] current_step = 0 found_cycle = False cycle_start = 0 cycle_length = 0 while current_step < L: if current_n in memo: # Cycle detected cycle_start = memo[current_n] cycle_length = current_step - cycle_start remaining = L - current_step remaining_in_cycle = remaining % cycle_length current_n = path[cycle_start + remaining_in_cycle] break memo[current_n] = current_step path.append(current_n) current_n = apply_shuffle(current_n, M) current_step += 1 print(f"{current_n:04d}") if __name__ == "__main__": solve()