No.2762 Counting and Deleting
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : 👑
binap
/ テスター :
magurofly
aplysiaSheep
タグ : / 解いたユーザー数 33
作問者 : 👑
![aplysiaSheep](https://pbs.twimg.com/profile_images/1755875215937265664/DA7ZDzYk.jpg)
問題文最終更新日: 2024-05-29 11:20:28
問題文
0
と1
のみからなる長さ の文字列 があります。クエリが 個与えられるので、与えられた順番に処理してください。
クエリは次の 種類のいずれかです。
1 l r
: (削除クエリ) を満たす全ての について を文字_
に変える。2 l r
: (数え上げクエリ) 自然数である文字列であって、 の連続部分列 の(連続とは限らない)部分列として現れるものが何種類あるか求める。自然数である文字列とは以下の条件を満たす文字列 のことを指す。- は空文字列ではない。
- は
0
でない。(つまりleading-zeroを認めない) - はいずれも
_
でない。
クエリ2で求める種類数はとても大きな値になる場合があるので素数 で割った余りを出力してください。
入力
入力は以下の形式で標準入力から与えられる。
はすべて0
または1
また各 は以下のどちらかの形で与えられる。
入力はすべて整数
注釈
出題時から問題文を少し変更しました。「整数である文字列」としていたものを「自然数である文字列」に変更してあります。名称のみの変更で題意やテストケースへの変更はありません。(2024/05/18 04:20)
出力
クエリ2の個数を 個として、 行出力せよ。 行目には 個目のクエリ2に対する答えを出力せよ。ただし素数 で割った余りを出力すること。
サンプル
サンプル1
入力
4 3 1010 2 1 4 1 2 2 2 1 4
出力
7 4
- 1番目のクエリで は
1010
です。自然数である部分列は1
、10
、11
、100
、101
、110
、1010
の 種類です。例えば文字列0
や01
などは自然数であるとは言わないことに注意してください。 - 2番目のクエリで は
1_10
となります。 - 3番目のクエリで は
1_10
です。自然数である部分列は1
、10
、11
、110
の 種類です。
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。