結果

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

ソースコード

diff # 

MOD = 10**9 + 7

n = int(input())
q = int(input())

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

valid_b_up_to = 0  # Initially, only b[0] is valid
b = [0] * (n + 1)
b[0] = 1

valid_S_up_to = 0  # Initially, S[0] is valid (0)
S = [0] * (n + 1)

for _ in range(q):
    parts = input().split()
    if parts[0] == 'x':
        i = int(parts[1])
        v = int(parts[2])
        x[i] = v
        valid_S_up_to = min(valid_S_up_to, i)
    elif parts[0] == 'y':
        i = int(parts[1])
        v = int(parts[2])
        y[i] = v
        valid_b_up_to = min(valid_b_up_to, i)
        valid_S_up_to = 0  # Invalidate entire S array
    else:
        i = int(parts[1])
        if i == 0:
            print(1)
            continue
        
        # Recompute b up to i-1 if necessary
        if valid_b_up_to < i - 1:
            for j in range(valid_b_up_to + 1, i):
                prev = j - 1
                if prev < 0:
                    b[j] = 1
                else:
                    b[j] = (y[prev] * b[prev] + 1) % MOD
            valid_b_up_to = i - 1
        
        # Recompute S up to i if necessary
        if valid_S_up_to < i:
            for j in range(valid_S_up_to + 1, i + 1):
                if j == 0:
                    S[j] = 0
                else:
                    prev_j = j - 1
                    term = (x[prev_j] * pow(b[prev_j], 2, MOD)) % MOD
                    S[j] = (S[j - 1] + term) % MOD
            valid_S_up_to = i
        
        res = (S[i] + 1) % MOD
        print(res)
0