結果
問題 | No.510 二次漸化式 |
ユーザー |
![]() |
提出日時 | 2017-04-28 23:47:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,123 bytes |
コンパイル時間 | 1,598 ms |
コンパイル使用メモリ | 170,136 KB |
実行使用メモリ | 13,600 KB |
最終ジャッジ日時 | 2024-09-13 18:43:43 |
合計ジャッジ時間 | 24,865 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 TLE * 1 -- * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long MOD = 1000000000 + 7;int main(){int n, q;cin >> n >> q;vector<long>x(n);vector<long>y(n);vector<long>a(n + 1);vector<long>b(n + 1);a[0] = 1;b[0] = 1;for (int i = 0; i < n; ++i) {a[i + 1] = (x[i] * ((b[i] * b[i]) % MOD) % MOD) + a[i];b[i + 1] = y[i] * b[i] + 1;a[i + 1] %= MOD;b[i + 1] %= MOD;}for (int t = 0; t < q; ++t) {char c;cin >> c;switch (c) {case 'x': {int idx, val;cin >> idx >> val;x[idx] = val;for (int i = idx; i < n; ++i) {a[i + 1] = (x[i] * ((b[i] * b[i]) % MOD) % MOD) + a[i];a[i + 1] %= MOD;}}break;case 'y': {int idx, val;cin >> idx >> val;y[idx] = val;for (int i = idx; i < n; ++i) {a[i + 1] = (x[i] * ((b[i] * b[i]) % MOD) % MOD) + a[i];b[i + 1] = y[i] * b[i] + 1;a[i + 1] %= MOD;b[i + 1] %= MOD;}}break;case 'a': {int idx;cin >> idx;cout << a[idx] << endl;}}}return 0;}