Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 298 D問題 Writing a Numeral

AtCoder ABC ABC298 D問題 400 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$S=1$ で初期化された文字列がある. 次の $Q$ 個のクエリを順に処理せよ.

Type 1: $S$ の末尾に数字 $x$ を追加する.
Type 2: $S$ の先頭の文字を削除する.
Type 3: $S$ を十進数表記の数とみなした整数を $998244353$ で割った余りを出力する

制約

$1 \leq Q \leq 6 \times 10^5$ .
Type 1
- $x$ は数字 $1,2,3,4,5,6,7,8,9$ のどれか.
Type 2
- $S$ の長さは $2$ 以上.
Type 3
- このタイプのクエリは存在する.

解法

$S$ をキューと見なす. このとき, 次のように処理することで, 高速に計算できる. ただし, $T$ を整数 $1$ で初期化し, $T$ が Type 3 における解答とする.

Type 1: $S$ の末尾に $x$ を追加し, $T \gets (10T+x)$ とする.
Type 2: $S$ の長さを $L$ とする. このとき, $S$ の先頭の要素を pop し, その要素を $a$ とする. そして, $T$ から $a \times 10^{L-1}$ を引く.
Type 3: $T$ を出力する.

ここで, $K$ は非常に大きくなるので, $T$ の更新と $10^{L-1}$ の計算においては $\bmod{998244353}$ で計算しなければならない.