結果
問題 |
No.2122 黄金比で擬似乱数生成
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:48:11 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,094 bytes |
コンパイル時間 | 445 ms |
コンパイル使用メモリ | 81,584 KB |
実行使用メモリ | 222,344 KB |
最終ジャッジ日時 | 2025-04-16 15:49:05 |
合計ジャッジ時間 | 5,779 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 TLE * 1 -- * 9 |
ソースコード
def main(): import sys S = sys.stdin.readline().strip() M = int(sys.stdin.readline()) L = int(sys.stdin.readline()) initial_n = int(S) # Precompute f(n) for all n in 0..9999 f = [0] * 10000 if M == 0: # For M=0, the result is always 0 for n in range(10000): f[n] = 0 else: for n in range(10000): # Compute b_M for this n if M == 1: b = 1 else: # Matrix exponentiation for the recurrence b_m = n*b_{m-1} + b_{m-2} def multiply(a, b): return [ [a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]], [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]] ] def matrix_power(mat, power): result = [[1, 0], [0, 1]] # Identity matrix while power > 0: if power % 2 == 1: result = multiply(result, mat) mat = multiply(mat, mat) power //= 2 return result mat = [[n, 1], [1, 0]] power = M - 1 mat_pow = matrix_power(mat, power) # Initial vector is [b_1, b_0] = [1, 0] b = mat_pow[0][0] * 1 + mat_pow[0][1] * 0 if M % 2 == 0: new_n = b else: new_n = b - 1 new_n %= 10000 f[n] = new_n # Precompute binary lifting table jump = [[0] * 10000 for _ in range(60)] for n in range(10000): jump[0][n] = f[n] for k in range(1, 60): for n in range(10000): jump[k][n] = jump[k-1][jump[k-1][n]] # Apply L steps using binary lifting current = initial_n for bit in range(60): if L & (1 << bit): current = jump[bit][current] # Convert to 4-digit string print(f"{current:04d}") if __name__ == "__main__": main()