問題一覧 > 通常問題

No.2762 Counting and Deleting

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 35
作問者 : 👑 binap / テスター : 👑 magurofly aplysiaSheep
お気に入りにしたユーザー ProblemId : 10913 / 自分の提出
問題文最終更新日: 2024-05-29 11:20:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 430 (順位表) の他の問題:

Problem Statement

There is a string $S_1S_2\ldots S_{N}$ of length $N$ consisting only of 0 and 1. You are given $Q$ queries; process them in the given order.

Each query is one of the following $2$ types.

  • 1 l r : (Deletion query) For every $i$ satisfying $l \leq i \leq r$, change $S_i$ to the character _.
  • 2 l r : (Counting query) Find the number of distinct natural-number strings that appear as a (not necessarily contiguous) subsequence of the substring $S[l:r]$ of $S$. A natural-number string is a string $X$ satisfying the following conditions.
    • $X$ is not the empty string.
    • $X_1$ is not 0. (That is, leading zeros are not allowed.)
    • None of $X_1,X_2,\ldots,X_{|X|}$ is _.

The number of distinct strings to be found in query 2 can be very large, so output it modulo the prime $998244353$.

Input

The input is given from standard input in the following format.

$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$ are all 0 or 1

Each $query_i$ is given in one of the following forms.

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

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

All input values are integers.

Notes

The problem statement has been slightly changed since the contest. What was called an "integer string" has been changed to a "natural-number string". Only the name has changed; there are no changes to the meaning of the problem or the test cases. (2024/05/18 04:20)

Output

Let $K$ be the number of type 2 queries. Output $K$ lines. On the $i$-th line, output the answer to the $i$-th type 2 query, modulo the prime $998244353$.

Sample

Sample 1
Input
4 3
1010
2 1 4
1 2 2
2 1 4
Output
7
4

  • In the 1st query, $S[1:4]$ is 1010. There are $7$ distinct subsequences that are natural numbers: 1, 10, 11, 100, 101, 110, 1010. Note that, for example, the strings 0 and 01 are not considered natural numbers.
  • After the 2nd query, $S$ becomes 1_10.
  • In the 3rd query, $S[1:4]$ is 1_10. There are $4$ distinct subsequences that are natural numbers: 1, 10, 11, 110.

Sample 2
Input
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
Output
1
6
0
2
2
0
0

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