P7495 Anagram Collapse

> The laws of nature are hidden in the darkness. Under the moonlight, Fiona and a group of believers who share the same faith gather together, waiting for the god they believe in to arrive. “Dear God, we are willing to follow you forever.”

The god wants to test whether his believers are loyal, and he decides to use luck as the test. The god has prepared $n$ questions in advance. Each question has two choices: **“relatively radical”** and **“relatively conservative”**. The god has already fixed his own choices. To test his believers, the god will **uniformly choose one** from all feasible ways of selecting questions (a feasible way means choosing **a consecutive** $k$ questions, with $l\leq k\leq r$, where $l,r$ are given). Then the believers will answer each of the $k$ questions in order with either “relatively radical” or “relatively conservative”. The god will judge whether a believer is loyal based on his own choices and that believer’s answers. The judging rules are: + This is the first question: no matter what the answer is, the god is willing to believe the believer is loyal. + This is not the first question: if the believer’s previous answer is the same as the god’s choice, then the god will require them to explore more advanced choices, so the believer’s answer to this question **cannot be more conservative than the god’s choice**; otherwise, the god will require the believer to obey him, so the believer’s answer to this question **cannot be more radical than the god’s choice**. If the believer’s answers satisfy the above requirements, then the believer is loyal. Now, the god wants to know: if a believer answers each question **uniformly at random with “relatively radical” or “relatively conservative”**, what is the probability that the believer is loyal? He asks you this question through Fiona, and requires you to output the result modulo $998244353$. If you cannot answer in time, you will lose the god’s trust. ------------ #### Simplified statement: Given a binary string $a$ of length $n$ and $l,r(l\leq r)$. For two binary strings $p,q$ of the same length $k$, we say that $q$ is “loyal” to $p$ if and only if $p$ and $q$ satisfy: + For any $1

The first line contains three integers $n,l,r$, as described above. The second line contains a string of length $n$, representing $a$. It is guaranteed that the string contains only characters `0` and `1`.

Output one integer in one line, representing the answer.

#### Explanation for Sample 1: We use $\left[l,r\right]$ to denote the interval where the chosen substring lies. + Choose $\left[1,2\right]$. The substring is `01`, with length $2$. There are $3$ binary strings that are “loyal” to this substring, so the probability is $\dfrac{3}{4}$. + Choose $\left[1,3\right]$. The substring is `011`, with length $3$. There are $4$ binary strings that are “loyal” to this substring, so the probability is $\dfrac{1}{2}$. + Choose $\left[2,3\right]$. The probability is $\dfrac{3}{4}$. + Choose $\left[2,4\right]$. The probability is $\dfrac{5}{8}$. + Choose $\left[3,4\right]$. The probability is $\dfrac{3}{4}$. + Choose $\left[3,5\right]$. The probability is $\dfrac{1}{2}$. + Choose $\left[4,5\right]$. The probability is $\dfrac{3}{4}$. So the result is $\dfrac{\dfrac{3}{4}+\dfrac{1}{2}+\dfrac{3}{4}+\dfrac{5}{8}+\dfrac{3}{4}+\dfrac{1}{2}+\dfrac{3}{4}}{7}=\dfrac{37}{56}$, which is $338690049$ modulo $998244353$. ------------ **This problem uses bundled testdata.** + Subtask 1 ( $1\%$ ): $n=1$. + Subtask 2 ( $13\%$ ): $n\leq100$. + Subtask 3 ( $3\%$ ): Guaranteed that $\forall1\leq i\leq n,a_i=0$. + Subtask 4 ( $3\%$ ): Guaranteed that $\forall1\leq i\leq n,a_i=1$. + Subtask 5 ( $20\%$ ): $n\leq10^3$. + Subtask 6 ( $15\%$ ): $l=r$. + Subtask 7 ( $20\%$ ): $n\leq 5\times 10^5$. + Subtask 8 ( $25\%$ ): No special constraints. Constraints: for all testdata, $1\leq n\leq5\times 10^6,1\leq l\leq r\leq n$。 Translated by ChatGPT 5