T1:数字字符串
本题难度中等,使用队列存储 \(s\) 的字符。用一个变量 \(r\) 维护 \(s\) 模 \(\bmod\) 的余数
- 对于操作 \(1\),直接 \(r = r*10 +x\) 后模 \(\bmod\)
- 对于操作 \(2\),设 \(s\) 此时有 \(k\) 位、首位是 \(a\),那么删除首位后, \(r\) 应该减少 \(a \cdot 10^{k-1}\)。
- 对于操作 \(3\),直接输出 \(r\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
int Q;
cin >> Q;
queue<int> q;
q.push(1);
mint ans = 1;
rep(qi, Q) {
int type;
cin >> type;
if (type == 1) {
int x;
cin >> x;
q.push(x);
ans = ans*10+x;
}
if (type == 2) {
int x = q.front(); q.pop();
ans -= mint(x)*mint(10).pow(q.size());
}
if (type == 3) {
cout << ans << '\n';
}
}
return 0;
}