No.2762 Counting and Deleting
タグ : / 解いたユーザー数 35
作問者 : 👑
aplysiaSheep
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 strings0and01are 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もしくは右上の雲マークをクリックしてアカウントを作成してください。