結果

問題 No.2122 黄金比で擬似乱数生成
ユーザー lam6er
提出日時 2025-03-20 20:52:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,683 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 223,952 KB
最終ジャッジ日時 2025-03-20 20:52:47
合計ジャッジ時間 6,756 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 8 RE * 2 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

S = input().strip()
M = int(input())
L = int(input())

current_state = int(S)

def multiply(mat1, mat2):
    a, b, c, d = mat1
    e, f, g, h = mat2
    return (
        a * e + b * g,
        a * f + b * h,
        c * e + d * g,
        c * f + d * h
    )

def matrix_pow(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

def calculate_a_M(n, M_val):
    if M_val == 0:
        return 2
    elif M_val == 1:
        return n
    a0 = 2
    a1 = n
    trans_matrix = (n, 1, 1, 0)
    powered = matrix_pow(trans_matrix, M_val - 1)
    a_M = powered[0] * a1 + powered[1] * a0
    return a_M

def precompute_f(M_val):
    f_table = [0] * 10000
    for n in range(10000):
        a_M = calculate_a_M(n, M_val)
        r = (n**2 + 4) ** 0.5
        if r == 0:
            x = 0
        else:
            x = a_M / r
        X = int(x // 1)
        next_n = X % 10000
        f_table[n] = next_n
    return f_table

if M == 0 and L == 0:
    print(S)
    exit()

f_table = precompute_f(M)

current = int(S)
visited = {}
steps = 0
found_cycle = False

while steps < L:
    if current in visited:
        cycle_start = visited[current]
        cycle_length = steps - cycle_start
        remaining = L - steps
        remaining %= cycle_length
        current = current
        for _ in range(remaining):
            current = f_table[current]
        break
    else:
        visited[current] = steps
        next_state = f_table[current]
        current = next_state
        steps += 1

print("{:04d}".format(current))
0