結果

問題 No.510 二次漸化式
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:46:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,439 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 81,956 KB
実行使用メモリ 80,768 KB
最終ジャッジ日時 2025-04-16 00:50:13
合計ジャッジ時間 15,020 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    q = int(input[ptr])
    ptr += 1
    
    x = [0] * n
    y = [0] * n
    
    for _ in range(q):
        query = input[ptr]
        ptr += 1
        if query == 'x':
            i = int(input[ptr])
            ptr += 1
            v = int(input[ptr])
            ptr += 1
            x[i] = v % MOD
        elif query == 'y':
            i = int(input[ptr])
            ptr += 1
            v = int(input[ptr])
            ptr += 1
            y[i] = v % MOD
        elif query == 'a':
            i = int(input[ptr])
            ptr += 1
            if i == 0:
                print(1)
                continue
            a = 1  # a_0
            b = 1  # b_0
            for k in range(i):
                # Compute a_{k+1} = x_k * b_k^2 + a_k
                # But we need to compute up to a_{i} = a_i, which is 1 + sum_{k=0 to i-1} x_k * b_k^2
                # So for query a_i, we need the sum up to k = i-1
                if k < i:
                    term = (x[k] * pow(b, 2, MOD)) % MOD
                    a = (a + term) % MOD
                # Compute b_{k+1}
                if k < n:
                    new_b = (y[k] * b + 1) % MOD
                    b = new_b
            print(a % MOD)
        else:
            assert False, "Invalid query type"

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