結果

問題 No.510 二次漸化式
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:10:20
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,426 ms / 3,000 ms
+ 160µs
コード長 1,269 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 225 ms
コンパイル使用メモリ 96,104 KB
実行使用メモリ 92,800 KB
最終ジャッジ日時 2026-07-12 02:29:54
合計ジャッジ時間 31,632 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 10**9 + 7

n = int(input())
q = int(input())
queries = [input().split() for _ in range(q)]

x = [0] * n
y = [0] * n

a = [0] * (n + 1)
b = [0] * (n + 1)
a[0] = 1
b[0] = 1

current_max = 0

for query in queries:
    if query[0] == 'x':
        i = int(query[1])
        v = int(query[2])
        if i + 1 <= current_max:
            current_max = i
        x[i] = v
    elif query[0] == 'y':
        i = int(query[1])
        v = int(query[2])
        if i <= current_max:
            current_max = i
        y[i] = v
    else:
        i = int(query[1])
        while current_max < i:
            current_max += 1
            if current_max == 0:
                a[current_max] = 1
                b[current_max] = 1
                continue
            # Compute b[current_max]
            y_val = y[current_max - 1]
            b_prev = b[current_max - 1]
            b_current = (y_val * b_prev) % MOD + 1
            b_current %= MOD
            b[current_max] = b_current
            # Compute a[current_max]
            a_prev = a[current_max - 1]
            x_val = x[current_max - 1]
            b_prev_sq = (b_prev * b_prev) % MOD
            a_current = (a_prev + x_val * b_prev_sq) % MOD
            a[current_max] = a_current
        print(a[i] % MOD)
0