問題一覧 > 通常問題

No.2762 Counting and Deleting

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : 👑 binapbinap / テスター : maguroflymagurofly aplysiaSheepaplysiaSheep
2 ProblemId : 10913 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-29 11:20:28

問題文

01のみからなる長さ $N$ の文字列 $S_1S_2\ldots S_{N}$ があります。クエリが $Q$ 個与えられるので、与えられた順番に処理してください。

クエリは次の $2$ 種類のいずれかです。

  • 1 l r : (削除クエリ) $l \leq i \leq r$ を満たす全ての $i$ について $S_i$ を文字_に変える。
  • 2 l r : (数え上げクエリ) 自然数である文字列であって、$S$ の連続部分列 $S[l:r]$ の(連続とは限らない)部分列として現れるものが何種類あるか求める。自然数である文字列とは以下の条件を満たす文字列 $X$ のことを指す。
    • $X$ は空文字列ではない。
    • $X_1$ は 0でない。(つまりleading-zeroを認めない)
    • $X_1,X_2,\ldots,X_{|X|}$ はいずれも _でない。

クエリ2で求める種類数はとても大きな値になる場合があるので素数 $998244353$ で割った余りを出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$
$S$
$query_1$
$query_2$
$\vdots$
$query_Q$

$1 \leq N \leq 6\times10^4$

$1 \leq Q \leq 6\times10^4$

$S_1,S_2,\ldots,S_N$ はすべて0または1

また各 $query_i$ は以下のどちらかの形で与えられる。

$1$ $l$ $r$
$2$ $l$ $r$

$1 \leq l \leq r \leq N$

入力はすべて整数

注釈

出題時から問題文を少し変更しました。「整数である文字列」としていたものを「自然数である文字列」に変更してあります。名称のみの変更で題意やテストケースへの変更はありません。(2024/05/18 04:20)

出力

クエリ2の個数を $K$ 個として、$K$ 行出力せよ。 $i$ 行目には $i$ 個目のクエリ2に対する答えを出力せよ。ただし素数 $998244353$ で割った余りを出力すること。

サンプル

サンプル1
入力
4 3
1010
2 1 4
1 2 2
2 1 4
出力
7
4

  • 1番目のクエリで $S[1:4]$ は1010です。自然数である部分列は110111001011101010の $7$ 種類です。例えば文字列001などは自然数であるとは言わないことに注意してください。
  • 2番目のクエリで $S$ は1_10となります。
  • 3番目のクエリで $S[1:4]$ は1_10です。自然数である部分列は11011110の $4$ 種類です。

サンプル2
入力
12 11
100000011100
1 3 3
2 6 8
2 8 11
2 12 12
2 3 9
2 1 2
1 2 9
2 2 9
1 6 6
1 5 10
2 3 7
出力
1
6
0
2
2
0
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。