結果

問題 No.1559 Next Rational
ユーザー lam6er
提出日時 2025-03-20 18:49:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 1,619 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 53,904 KB
最終ジャッジ日時 2025-03-20 18:51:44
合計ジャッジ時間 1,434 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    N, A, B, K = map(int, sys.stdin.readline().split())
    if N == 1:
        print(A % MOD)
        return
    if N == 2:
        print(B % MOD)
        return
    
    # Mod values for A, B, K
    A_mod = A % MOD
    B_mod = B % MOD
    K_mod = K % MOD
    
    # Compute p = (A^2 + B^2 + K) / (A*B) mod MOD
    numerator = (pow(A_mod, 2, MOD) + pow(B_mod, 2, MOD) + K_mod) % MOD
    denominator = (A_mod * B_mod) % MOD
    denominator_inv = pow(denominator, MOD-2, MOD)
    p = (numerator * denominator_inv) % MOD
    
    # Define matrix multiplication
    def multiply(m1, m2):
        a = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD
        b = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % MOD
        c = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % MOD
        d = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % MOD
        return [[a, b], [c, d]]
    
    # Matrix exponentiation
    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
    
    # Initialize the transformation matrix
    mat = [
        [p, (MOD - 1) % MOD],
        [1, 0]
    ]
    
    # Compute matrix raised to (N-2)th power
    power = N - 2
    mat_pow = matrix_power(mat, power)
    
    # Compute a_n: mat_pow[0][0] * B_mod + mat_pow[0][1] * A_mod
    a_n = (mat_pow[0][0] * B_mod + mat_pow[0][1] * A_mod) % MOD
    print(a_n)

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