結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:00:35 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,773 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,476 KB |
実行使用メモリ | 88,700 KB |
最終ジャッジ日時 | 2025-06-12 16:01:13 |
合計ジャッジ時間 | 35,218 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 TLE * 8 -- * 12 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read data = input().split() ptr = 0 n = int(data[ptr]) ptr +=1 q = int(data[ptr]) ptr +=1 max_i = n x = [0] * (n) y = [0] * (n) a_sum = [0] * (n+2) b = [0] * (n+2) b[0] = 1 a_sum[0] = 1 for i in range(1, n+1): prev_b = b[i-1] % MOD yi = y[i-1] % MOD new_b = (yi * prev_b + 1) % MOD b[i] = new_b xi = x[i-1] % MOD term = (xi * (prev_b ** 2 % MOD)) % MOD a_sum[i] = (a_sum[i-1] + term) % MOD for _ in range(q): query = data[ptr] ptr +=1 if query == 'x': i = int(data[ptr]) ptr +=1 v = int(data[ptr]) ptr +=1 x[i] = v for j in range(i+1, n+1): prev_b = b[j-1] yi = y[j-1] new_b = (yi * prev_b + 1) % MOD b[j] = new_b xi = x[j-1] term = (xi * (prev_b ** 2 % MOD)) % MOD a_sum[j] = (a_sum[j-1] + term) % MOD elif query == 'y': i = int(data[ptr]) ptr +=1 v = int(data[ptr]) ptr +=1 y[i] = v for j in range(i+1, n+1): prev_b = b[j-1] yi = y[j-1] new_b = (yi * prev_b + 1) % MOD b[j] = new_b xi = x[j-1] term = (xi * (prev_b ** 2 % MOD)) % MOD a_sum[j] = (a_sum[j-1] + term) % MOD elif query == 'a': i = int(data[ptr]) ptr +=1 print(a_sum[i] % MOD) if __name__ == '__main__': main()