結果

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

ソースコード

diff # 

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