题目描述

难度分:$943$

最初$S=1$。
输入$q(\leq 6 \times 10^5)$和$q$个操作，操作的输入格式如下：

1. 如果输入的是1 x，把$x$加到$S$末尾。其中$1 \leq x \leq 9$。

2. 如果输入的是2，删除$S$的第一个数字。

3. 如果输入的是3，把$S$视作一个整数，输出它模$998244353$的结果。

输入样例$1$

3
3
1 2
3

输出样例$1$

1
12

输入样例$2$

3
1 5
2
3

输出样例$2$

5

输入样例$3$

11
1 9
1 9
1 8
1 2
1 4
1 4
1 3
1 5
1 3
2
3

输出样例$3$

0

算法

队列模拟

用队列来存储$S$，初始情况下，队列中只有一个$1$。记队列中元素所表示的数字为$num$，三种操作按照如下规则：

1. 如果是插入操作，则有$num=(10 \times num \% mod + x) \% mod$，并将$x$尾插进队列。
2. 如果是删除操作，则弹出队头元素$d$，此时$d$代表的应该是$d \times 10^{sz}$，其中$sz$为队列弹出$d$后的大小。则有$num=(num-d \times 10^{sz} + mod) \% mod$。
3. 打印操作直接打印$num$即可。

为了快速进行操作$2$，可以先预处理出一个$10$的整次幂数组$p$，$p[i]$表示$10^i \% mod$。

复杂度分析

时间复杂度

令$p[0]=1$，然后线性遍历幂次来计算$p[i]$，因此预处理出$10$的整次幂数组$p$的时间复杂度为$O(n)$。记操作次数为$q$的规模，队头弹出和队尾插入的时间复杂度都是$O(1)$的，每个操作里面的计算也都是$O(1)$的，因此算法整体的时间复杂度就是$O(n+q)$。

空间复杂度

空间消耗的痛点就是队列和数组$p$，最差情况下没有弹出操作，全是队列的插入操作，额外空间复杂度为$O(n+q)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long LL;

const int MOD = 998244353, N = 600010;
LL p[N];

LL fast_power(LL a, LL k, LL p) {
    LL res = 1 % p;
    while(k) {
        if(k & 1) res = (LL)res*a%p;
        a = (LL)a*a%p;
        k >>= 1;
    }
    return res;
}

int main() {
    if(!p[0]) {
        // 只预处理一次
        p[0] = 1;
        for(int i = 1; i <= N - 10; i++) {
            p[i] = p[i - 1]*10%MOD;
        }
    }
    int Q;
    scanf("%d", &Q);
    LL num = 1;
    queue<int> q;
    q.push(1);
    while(Q--) {
        int t;
        scanf("%d", &t);
        if(t == 1) {
            int x;
            scanf("%d", &x);
            q.push(x);
            num = (num*10%MOD + x) % MOD;
        }else if(t == 2) {
            int d = q.front();
            q.pop();
            int sz = q.size();
            num = (num - p[sz]*d%MOD + MOD) % MOD;
        }else {
            printf("%lld\n", num);
        }
    }
    return 0;
}