結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:10:20 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,269 bytes |
コンパイル時間 | 282 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 83,684 KB |
最終ジャッジ日時 | 2025-06-12 21:11:58 |
合計ジャッジ時間 | 40,417 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 TLE * 5 |
ソースコード
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)