Background

dottle bot。

Problem Description

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\}$.

Input Format

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.

Output Format

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$.

2 0 1 2
10

3034

14 1 14 13
10110101110101

379883349

Hint

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