結果

問題 No.2122 黄金比で擬似乱数生成
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0