P9055 [CTT Mutual Test 2021] Sequence Rearrangement.

dottle bot。

Define the $\textrm{mex}$ of an interval of a sequence as the smallest natural number that does not appear in the interval. Define the value of a sequence as the number of intervals whose $\textrm{mex}\geq k$. Given $n$ natural numbers less than $m$ and an interval $[l,r]$, let $f(k)$ denote, among all permutations of the sequence formed by these $n$ numbers, the maximum possible value of the sequence. For each $k\in [l,r]$, find $f(k)$. Let $a_i$ denote the number of occurrences of number $i$. It is guaranteed that there exists a positive integer $X$ such that $\forall i\le m-1,a_i\in \{X,X+1\}$.

Since $n$ may be very large, the following method is used to reduce input size: The first line contains four integers $m,l,r,X$. The second line contains a binary string of length $m$. If the $i$-th position is $1$, then the number of occurrences of $i-1$ is $X+1$; otherwise, the number of occurrences is $X$. From the input, we can derive $n=mX+S$, where $S$ is the number of $1$'s in the binary string.

To reduce output size, let $ans=\displaystyle{\bigoplus_{i=l}^r} (233^if(i)\bmod 998244353)$, where $\displaystyle\bigoplus$ denotes bitwise XOR in binary. Output one line containing the integer $ans$.

#### Explanation for Sample 1 In the sample sequence, there are $3$ zeros and $2$ ones. For any permutation, $f(0)$ is always $15$. When the permutation is $\textrm{01010}$, $f(1)$ reaches its maximum value $13$. The answer is: $$ \displaystyle (233^0\times 15\bmod 998244353)\oplus(233^1\times 13\bmod 998244353)=3034 $$ #### Constraints - Subtask 1 (5 points): $n,m\leq 9$. - Subtask 2 (15 points): $n,m\leq 200$. - Subtask 3 (15 points): $n,m\leq 5\times 10^3$. - Subtask 4 (5 points): $m\leq 2$，$l=0$，$r=1$。 - Subtask 5 (10 points): $m\leq 10^6$，$l=m$，$r=m$。 - Subtask 6 (10 points): $m\leq 10^6$，$X=1$，$s_i=0$。 - Subtask 7 (15 points): $m\leq 10^6$，$r-l+1\leq 10^4$。 - Subtask 8 (15 points): $m\leq 2\times 10^6$。 - Subtask 9 (10 points): No special constraints. For all testdata, it holds that $n\leq 10^9$, $m\leq 10^7$, $0\leq l\leq r\leq m$, $X\geq 1$. Translated by ChatGPT 5