結果
問題 |
No.2122 黄金比で擬似乱数生成
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:46:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 1,893 bytes |
コンパイル時間 | 452 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 54,396 KB |
最終ジャッジ日時 | 2025-04-16 15:47:46 |
合計ジャッジ時間 | 1,883 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
def compute_next_s(current_s, M): n = int(current_s) mod = 10000 if M == 0: return "0000" 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 //= 2 return result a = [[n, 1], [1, 0]] power = M - 1 mat = matrix_pow(a, power, mod) c_M_mod = (mat[0][0] * 1 + mat[0][1] * 0) % mod integer_part = (c_M_mod - (M % 2)) % mod return f"{integer_part:04d}" def main(): import sys input = sys.stdin.read().split() S = input[0] M = int(input[1]) L = int(input[2]) current_s = S history = [] pos_map = {} loop_found = False remaining = L history.append(current_s) pos_map[current_s] = 0 for i in range(1, L + 1): next_s = compute_next_s(current_s, M) if next_s in pos_map: loop_start = pos_map[next_s] loop_length = i - loop_start remaining = L - i if loop_length == 0: current_s = next_s break remaining %= loop_length current_s = history[loop_start + remaining] break pos_map[next_s] = i history.append(next_s) current_s = next_s if i == L: current_s = next_s break print(current_s) if __name__ == "__main__": main()