#include #include #define MOD 998244353 using namespace std; typedef long long ll; int n, q; string pw; int type, low, high, v1, v2; ll p10[1000006]; ll tree[10][4000006]; int lazy[10][4000006]; ll inv(ll x) { ll res = 1; for (int i = 29; i >= 0; i--) { res = (res * res) % MOD; if ((MOD - 2) & (1 << i)) { res = (x * res) % MOD; } } return res; } void init(int idx, int s, int e) { if (s == e) { tree[pw[s] - '0'][idx] = p10[n - s - 1]; for (int i = 0; i < 10; i++) { lazy[i][idx] = -1; } return; } int mid = (s + e) / 2; init(2 * idx, s, mid); init(2 * idx + 1, mid + 1, e); for (int i = 0; i < 10; i++) { tree[i][idx] = (tree[i][2 * idx] + tree[i][2 * idx + 1]) % MOD; lazy[i][idx] = -1; } } void busy(int idx, int s, int e) { for (int i = 0; i < 10; i++) { if (lazy[i][idx] != -1) { tree[lazy[i][idx]][idx] = (tree[lazy[i][idx]][idx] + tree[i][idx]) % MOD; tree[i][idx] = 0; if (s != e) { lazy[i][2 * idx] = lazy[i][idx]; lazy[i][2 * idx + 1] = lazy[i][idx]; } lazy[i][idx] = -1; } } } void update(int idx, int s, int e, int l, int r, int from, int to) { busy(idx, s, e); if (s > r || e < l) { return; } if (l <= s && e <= r) { lazy[from][idx] = to; busy(idx, s, e); return; } int mid = (s + e) / 2; update(2 * idx, s, mid, l, r, from, to); update(2 * idx + 1, mid + 1, e, l, r, from, to); for (int i = 0; i < 10; i++) { tree[i][idx] = (tree[i][2 * idx] + tree[i][2 * idx + 1]) % MOD; } } ll query(int idx, int s, int e, int l, int r) { busy(idx, s, e); if (s > r || e < l) { return 0; } if (l <= s && e <= r) { ll res = 0; for (int i = 0; i < 10; i++) { res = (res + i * tree[i][idx]) % MOD; } return res; } int mid = (s + e) / 2; return (query(2 * idx, s, mid, l, r) + query(2 * idx + 1, mid + 1, e, l, r)) % MOD; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> pw; n = pw.size(); p10[0] = 1; for (int i = 1; i <= n; i++) { p10[i] = (10 * p10[i - 1]) % MOD; } init(1, 0, n - 1); cin >> q; for (int i = 0; i < q; i++) { cin >> type >> low >> high; low--; high--; if (type == 1) { cin >> v1 >> v2; update(1, 0, n - 1, low, high, v1, v2); } else { ll res = query(1, 0, n - 1, low, high); cout << (res * inv(p10[n - high - 1])) % MOD << "\n"; } } return 0; }

제출 #131519

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: