結果

問題 No.1275 綺麗な式
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:44:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 1,194 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 54,448 KB
最終ジャッジ日時 2025-03-20 18:44:36
合計ジャッジ時間 4,155 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

a, b = map(int, input().split())
n = int(input())

if n == 0:
    print(2 % MOD)
elif n == 1:
    print((2 * a) % MOD)
else:
    p = (2 * a) % MOD
    a_sq = (a * a) % MOD
    a_sq_minus_b = (a_sq - b) % MOD
    q = (-a_sq_minus_b) % MOD  # Ensure q is positive

    # Define matrix [[p, q], [1, 0]]
    def multiply(mat1, mat2):
        res = [[0]*2 for _ in range(2)]
        res[0][0] = (mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0]) % MOD
        res[0][1] = (mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1]) % MOD
        res[1][0] = (mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0]) % MOD
        res[1][1] = (mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1]) % MOD
        return res

    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

    exponent = n - 1
    mat = [[p, q], [1, 0]]
    mat_pow = matrix_power(mat, exponent)

    x1 = (2 * a) % MOD
    x0 = 2 % MOD
    xn = (mat_pow[0][0] * x1 + mat_pow[0][1] * x0) % MOD
    print(xn)
0