本問のように \(998244353\) で割った余りを扱う問題では、modintと呼ばれる構造体を用いて余りを取る操作を自動的に行うのが便利です。AtCoder Libraryにもそのような構造体があるため、(公式ドキュメントに従って)下のようにエイリアス宣言をした上でこれを用いるものとします。

using mint = modint998244353;

数字のみからなる文字列 \(S\) に対し、これを十進数表記の値とみなした値を \(998244353\) で割った余りを求めるには以下のようにすれば良いです。

1. 値を表す変数 \(ans\) を \(0\) で初期化する
2. \(i=1,2,\ldots,|S|\) の順に、「\(ans\) を \(10 \times ans + S_i\) に置き換える」という操作をする( \(S_i\) は \(S\) の上から \(i\) 桁目)

ただし、これには \(|S|\) ステップかかるため、\(3\) 種類目のクエリのたびに実行すると \(\mathrm{O}(Q^2)\) となり、実行時間制限に間に合わなくなってしまいます。

そこで、\(ans\) を常に保持し、\(1,2\) 種類目のクエリが来たら差分を考えて更新することにします。\(1\) 種類目のクエリに対しては \(ans\) を \(10 \times ans + x\) に置き換えれば良いです。\(2\) 番目のクエリに対しては (先頭の数字) \(\times 10^{|S|-1}\) を \(ans\) から引いた上で先頭の数字を削除すれば良いです。ただし、以下の \(2\) 点に注意してください。

• stringやvectorで先頭を削除する操作のステップ数は要素数に比例します。そのため、代わりにdequeなどを用いる必要があります。
• \(10^{|S|-1}\) を毎回愚直に求めると \(1\) 種類目のクエリが \(3 \times 10^5\) 個来た後で \(3\) 種類目のクエリが \(3 \times 10^5\) 個来る場合等に \(\mathrm{O}(Q^2)\) となります。\(i=0,1,2,\ldots\) に対する \(10^i\) の値を前計算するか、繰り返し二乗法を用いましょう(ACLのmodintのpowでは繰り返し二乗法によって累乗を求める仕様なので、実装例ではそれを用いています)。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
using namespace std;

int main() {
	
	int Q;
	cin>>Q;
    
	deque<int> S(1,1);
	mint ans = 1;
	
	for(int i=0;i<Q;i++){
		int t;
		cin>>t;
		if(t==1){
			int x;
			cin>>x;
			S.push_back(x);
			ans = ans*10 + x;
		}
		if(t==2){
			ans -= mint(10).pow(S.size()-1) * S.front();
			S.pop_front();
		}
		if(t==3){
			cout<<ans.val()<<endl;
		}
	}
	
	return 0;
}