P7279 Prism Shards.

Shards drift around in the boy’s world. In the end, they are collected by the boy, becoming a sequence of seemingly meaningless characters.

The boy only has one string $S$, with length $n$, indexed from $1 \dots n$; and an array $a_{1\dots n}$. The boy wrote down two numbers $L, R$ and tried to find those shards that have been lit by light: For two substrings $(S_{l_1\dots r_1}, S_{l_2\dots r_2})$ in $S$ that occur at different positions but are identical in content, if $L \le (a_{r_1} \oplus a_{r_2}) + (r_1 - l_1 + 1) \le R$, then there is light between these two substrings. Here, $S_{l\dots r}$ denotes the substring formed by concatenating the characters of $S$ with indices in $[l, r]$ in order, and $\oplus$ denotes the bitwise XOR operation. The boy wants to know how many pairs of substrings have light between them. Substring pairs are unordered. Specifically, $(S_{l_1\dots r_1}, S_{l_2\dots r_2})$ and $(S_{l_2\dots r_2}, S_{l_1\dots r_1})$ are considered the same pair. You only need to output the answer modulo $998244353$.

The first line contains a positive integer $n$. The second line contains a string $S$. The third line contains $n$ non-negative integers $a_{1\dots n}$. The fourth line contains two non-negative integers $L, R$.

One line containing a non-negative integer, which is the answer.

Constraints: For $20\%$ of the testdata, $n \le 100$; For $50\%$ of the testdata, $n \le 10^3$; For $100\%$ of the testdata, $1 \le n \le 10^5$, $0 \le a_i, L, R \le 10^5$, $L \le R$, and $S$ contains only lowercase letters. **"A gift from the problem setter"** Be a bit braver. Trust the constant factor of some algorithm. What you think of might be a trash standard solution. Translated by ChatGPT 5