이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())
typedef long long ll;
const int M = 1e9 + 7;
vector<vector<int>> mul(const vector<vector<int>> &a, const vector<vector<int>> &b) {
vector<vector<int>> res(4, vector<int>(4, 0));
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 4; ++k) {
res[i][j] += (ll)a[i][k] * b[k][j] % M;
if (res[i][j] >= M) res[i][j] -= M;
}
}
}
return res;
}
vector<vector<int>> get(int d) {
vector<vector<int>> res(4, vector<int>(4, 0));
for (int i = 0; i < 4; ++i) {
int good = (i & 1), bad = (i & 2);
for (int x = 0; x < 10; ++x) {
if (x > d && !good) break;
if (x == 3 && bad) continue;
int good1 = good, bad1 = 0;
if (x < d) good1 = 1;
if (x == 1) bad1 = 1;
++res[i][good1 + bad1 * 2];
}
}
return res;
}
const int N = 1e5 + 7;
vector<vector<int>> t[N];
string s;
void build(int v, int tl, int tr) {
if (tr - tl == 1) t[v] = get(s[tl] - '0'); else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm, tr);
t[v] = mul(t[2 * v], t[2 * v + 1]);
}
}
void update(int v, int tl, int tr, int pos, char x) {
if (tr - tl == 1) {
s[tl] = x;
t[v] = get(x - '0');
} else {
int tm = (tl + tr) / 2;
if (pos < tm) update(2 * v, tl, tm, pos, x); else update(2 * v + 1, tm, tr, pos, x);
t[v] = mul(t[2 * v], t[2 * v + 1]);
}
}
vector<vector<int>> query(int v, int tl, int tr, int l, int r) {
if (tl >= r || tr <= l) return {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
if (tl >= l && tr <= r) return t[v];
int tm = (tl + tr) / 2;
return mul(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm, tr, l, r));
}
int get_ans(const vector<vector<int>> &res) {
int ans = 0;
for (int i = 0; i < 4; ++i) {
ans += res[0][i];
if (ans >= M) ans -= M;
}
return ans;
}
int main() {
#ifdef ONPC
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q >> s;
build(1, 0, n);
cout << get_ans(t[1]) << '\n';
while (q--) {
int type;
cin >> type;
if (type == 1) {
int l, r;
cin >> l >> r;
--l;
cout << get_ans(query(1, 0, n, l, r)) << '\n';
} else {
int pos;
string x;
cin >> pos >> x;
--pos;
update(1, 0, n, pos, x[0]);
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |