結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:10:59 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,311 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 91,824 KB |
最終ジャッジ日時 | 2025-06-12 21:12:40 |
合計ジャッジ時間 | 18,214 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 TLE * 1 -- * 19 |
ソースコード
MOD = 10**9 + 7 n = int(input()) q = int(input()) queries = [input().split() for _ in range(q)] x = [0] * n y = [0] * n x_ptr = [0] * n y_ptr = [0] * n a = [0] * (n + 1) b = [0] * (n + 1) a[0] = 1 b[0] = 1 for i in range(1, n+1): b_prev = b[i-1] y_i_minus1 = y[i-1] b[i] = (y_i_minus1 * b_prev + 1) % MOD for i in range(1, n+1): x_prev = x[i-1] b_prev = b[i-1] term = (x_prev * pow(b_prev, 2, MOD)) % MOD a[i] = (a[i-1] + term) % MOD for query in queries: if query[0] == 'x': i = int(query[1]) v = int(query[2]) x[i] = v for j in range(i+1, n+1): b_prev = b[j-1] y_j_minus1 = y[j-1] b[j] = (y_j_minus1 * b_prev + 1) % MOD x_j_minus1 = x[j-1] term = (x_j_minus1 * pow(b[j-1], 2, MOD)) % MOD a[j] = (a[j-1] + term) % MOD elif query[0] == 'y': i = int(query[1]) v = int(query[2]) y[i] = v for j in range(i+1, n+1): b_prev = b[j-1] y_j_minus1 = y[j-1] b[j] = (y_j_minus1 * b_prev + 1) % MOD x_j_minus1 = x[j-1] term = (x_j_minus1 * pow(b[j-1], 2, MOD)) % MOD a[j] = (a[j-1] + term) % MOD elif query[0] == 'a': i = int(query[1]) print(a[i] % MOD)