結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()