P8151 The Other Shore | To See the Next Part of the Dream

「“To see the next part of the dream”…？」 “Yes… ‘Even though the body is already an adult, the heart is still that unrealistic child, still that child who believes they have endless possibilities— even after recognizing the gap between reality and ideals, it is still so. The dream of becoming a rock superstar from youth now seems especially out of reach, and one can only see the next part of the dream while moving forward again and again’… Don’t you think the author is a lot like me?” “The younger me was curious and happy about everything unknown, but now it feels like I am just clinging to dreams that go against reality like grabbing a lifeline, and then gradually seeing the next part of the dream in the current of life… Knowing my own failure, I still climb upward as if to see something or achieve something. In that case, I am not much different from the ‘active loser’ described by the author…” 「So, what exactly is it that you hope to see, and hope to achieve?」 “…” “Right now, I don’t know anymore.” > 나의 어리고 멍청했던 날들은 사라져줬으면 > > If only those young and foolish days would disappear. > > 나의 소중한 인연들 이제는 추억속으로만 > > Precious bonds now exist only in memories. > > 만약 이 세상이 전부 누군가의 또다른 꿈이었다면 > > If this world was entirely someone else’s another dream. > > 언젠가 깨어나게 될때 나는 지금과는 달라져있을까 > > When I wake up someday, will I be different from who I am now.

「Then, do you believe in destiny?」 “That kind of thing is, at most, just a lyrical tool in some motivational story.” 「Is that so… then do you want to play tarot cards?」 “Who would be interested in that…” 「Seriously, if you keep acting like you don’t care about anything, I’m going to get mad…！」 “Fine, fine… So? The tarot cards?” 「Well… hehe, imagine it yourself～」 “What is wrong with you…” 「Now there are $n$ piles of tarot cards on the table. Each pile has $2^n$ cards. From the table upward, they are pile $1$, pile $2$… pile $n$. Now, as the managers of destiny, we are going to shuffle these tarot cards once!」 “So… is the chuunibyou (pinyin: zhōng èr bìng) contagious now…” 「The shuffling process is as follows: split the deck evenly into two halves, holding the lower half and the upper half in the left and right hands respectively; then, the right hand drops one card from the bottom, the left hand drops one card from the bottom, the right hand drops one card from the bottom… alternating like this repeatedly. Then one shuffle is completed!」 “For example, when $n=2$, suppose the original cards from bottom to top are $[1,2,3,4]$. After one shuffle it becomes $[3,1,4,2]$—is that correct?” 「Yes! Then, for these $n$ piles of tarot cards, each initially arranged in order from bottom to top, I will not operate on the first pile, shuffle the second pile once, shuffle the third pile twice… and shuffle the $n$-th pile $n-1$ times. Next, I will deal these $n$ piles from bottom to top to $2^n$ people—meaning the first person gets the first card of each pile, the second person gets the second card of each pile… Each person gets exactly $n$ cards.」 「Now, define a person’s luck value as the number of cards they receive whose numbers are the same as their own person number. Can you compute the total sum of luck values over these $2^n$ people?」 “Hmm… setting aside your sloppy story, this problem is quite interesting.” 「That’s enough, hey!」 “… Thinking about it, it seems pretty simple. Let the total sum of luck values when $n=k$ be $f(k)$. Now you need to compute the sum of $f(k)$ for $l\le k\le r$. How about that?” 「… I can’t do it anymore…」 ### Brief statement For a sequence $a$ of length $2k$, define the function $S_q(a)$, where $$ S_q(a)= \begin{cases} a,&q=0\\ [a_{k+1},a_1,a_{k+2},a_2,\dots,a_{2k},a_k],&q=1\\ S_{q-1}(S_1(a)),&\text{otherwise.} \end{cases} $$ Now given positive integers $l,r$, compute $\sum_{k=l}^r f(k)$, where $$ f(n)=\sum_{q=0}^{n-1}\sum_{k=1}^{2^n}\left[S_q([1,2,3,\dots,2^n])_k=k\right] $$

One line with two positive integers $l,r$, representing the starting and ending indices of the sum.

Output one line with one positive integer, representing $\sum_{k=l}^rf(k)$. Take the answer modulo $998244353$.

### Sample explanation Take computing $f(2)$ in sample 1 as an example. Initially there are $2$ piles of cards, and in both piles the cards from bottom to top are $[1,2,3,4]$. Then we do nothing to the first pile, and shuffle the second pile once, so the second pile becomes $[3,1,4,2]$ from bottom to top. Now deal the two piles to $4$ people. The first person gets $[1,3]$, the second person gets $[2,1]$, the third person gets $[3,4]$, and the fourth person gets $[4,2]$. We find that each person’s luck value is $1$ (each person gets exactly one card whose number equals their own), so the total sum of luck values is $4$, hence $f(2)=4$. ### Constraints For all data, $1\le l\le r\le 10^{10}$. Subtask 1 (10 pts): guaranteed $l=r$ and $r\le 12$. Subtask 2 (35 pts): guaranteed $l=r$. Subtask 3 (15 pts): guaranteed $1\le l\le r\le 10^6$. Subtask 4 (40 pts): no special constraints. Translated by ChatGPT 5