結果

問題 No.2122 黄金比で擬似乱数生成
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:49:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,852 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 71,960 KB
最終ジャッジ日時 2025-03-31 17:50:39
合計ジャッジ時間 2,369 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def multiply_matrix(a, b, mod):
    res = [[0]*2 for _ in range(2)]
    res[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod
    res[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod
    res[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod
    res[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod
    return res

def matrix_power(mat, power, mod):
    result = [[1,0], [0,1]]  # Identity matrix
    while power > 0:
        if power % 2 == 1:
            result = multiply_matrix(result, mat, mod)
        mat = multiply_matrix(mat, mat, mod)
        power = power // 2
    return result

def compute_new_n(n, M, mod):
    if M == 0:
        return 0 % mod
    mat = [[n, 1], [1, 0]]
    power = M - 1
    mat_pow = matrix_power(mat, power, mod)
    # Multiply with [1, 0] vector
    b_m = (mat_pow[0][0] * 1 + mat_pow[0][1] * 0) % mod
    return b_m

def main():
    S = input().strip()
    M = int(input().strip())
    L = int(input().strip())
    current_n = int(S)
    mod = 10000

    history = []
    found_cycle = False
    cycle_start = 0
    cycle_length = 0

    for _ in range(L):
        # Check if current_n is in history to find cycle
        if current_n in history:
            idx = history.index(current_n)
            cycle_start = idx
            cycle_length = len(history) - idx
            remaining = L - _
            total_remaining = remaining
            final_pos = idx + (total_remaining) % cycle_length
            current_n = history[final_pos]
            found_cycle = True
            break
        history.append(current_n)
        # Compute new_n
        new_n = compute_new_n(current_n, M, mod)
        current_n = new_n

    if not found_cycle:
        current_n = current_n % mod

    # Format the result to 4 digits
    print("{:04d}".format(current_n))

if __name__ == "__main__":
    main()
0