P8151 彼岸 | To See the Next Part of the Dream

「“看见梦境的下一个部分”…？」 “是啊… ‘尽管身体已是成年人，但内心却依旧是那个不切实际的小孩，依旧是那个相信自己有着无尽可能的小孩——即使是在认清了现实和理想的鸿沟后，还仍是如此。年少时那个成为摇滚巨星的梦，如今已显得分外不可及，只能在一次次前行中看见梦的下一个部分’… 不觉得作者和我很像吗？” “曾经年少的自己对一切的未知都怀揣着好奇与欣喜，但如今仿佛只是在如同抓住救命稻草一般抓住自己背离现实的梦想，然后在生活的洋流中逐渐看见梦的下一个部分… 明知自己的失败，却仍在仿佛为了看见什么、达成什么一样向上登攀，这样一来，和作者所描述的‘active loser’也没什么两样吧…” 「所以，你所期望看见的、期望达成的，究竟是什么呢？」 “…” “现在的我，已经不知道了。” > 나의 어리고 멍청했던 날들은 사라져줬으면 > > 如果那些年少无知的日子消失掉就好了 > > 나의 소중한 인연들 이제는 추억속으로만 > > 珍贵的感情 现在仅仅存在于在记忆中 > > 만약 이 세상이 전부 누군가의 또다른 꿈이었다면 > > 如果这个世界 只是别人的梦 > > 언젠가 깨어나게 될때 나는 지금과는 달라져있을까 > > 某天醒来时 我会变得不一样吗

「那么，你相信宿命吗？」 “那种东西，顶多只是什么励志故事里的抒情工具吧。” 「是吗… 那么要玩玩塔罗牌吗？」 “谁会对那种事情感兴趣…” 「真是的，你要再一副对什么事情都漠不关心的态度我要生气了…！」 “好好好… 所以呢？塔罗牌呢？” 「这个嘛… 嘿嘿，自己想象咯～」 “什么毛病…” 「现在有 $n$ 叠塔罗牌放在桌上，每一叠都有 $2^n$ 张，从桌面向上分别是 $1$ 号、$2$ 号… $n$ 号。现在作为宿命的管理者的我们——要洗一遍这些塔罗牌！」 “怎么… 中二病开始传染了吗…” 「那么，洗牌的过程是，将牌均匀地分成两半，下面一半和上面一半分别放在左右手；接着，右手从底部放下一张牌，左手从底部放下一张牌，右手又从底部放下一张牌… 这样交错重复，于是一次洗牌就完成了！」 “例如 $n=2$ 时，假设原来的牌从下往上看是 $[1,2,3,4]$，洗一次牌后就会变成 $[3,1,4,2]$——是这样吗？” 「是的！然后对于这 $n$ 叠初始时都按顺序从下到上摆放的塔罗牌，我会不操作第一叠牌，然后洗一次第二叠牌，洗两次第三叠牌… 洗 $n-1$ 次第 $n$ 叠牌。接下来，我会把这 $n$ 叠牌都从下到上地发给 $2^n$ 个人——也就是说第一个人会拿到每叠牌的第一张，第二个人会拿到每叠牌的第二张… 每一个人都恰好会拿到 $n$ 张牌。」 「现在，定义一个人拿到和自己号码相同的牌的张数为这个人的幸运值。你能算出这 $n$ 个人幸运值的总和是多少吗？」 “嗯… 撇开你粗制滥造的题面不谈，这个题目还是很有趣的。” 「适可而止啊喂！」 “… 我想了想，好像还挺简单的。不妨让我们记 $n=k$ 的时候的幸运值总和为 $f(k)$。现在你需要对 $l\le k\le r$ 的 $f(k)$ 求和，你看怎么样？” 「… 不是很会了…」 ### 简要题意 对于长度为 $2k$ 的序列 $a$，定义函数 $S_q(a)$，其中 $$ 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} $$ 现在给定正整数 $l,r$，求 $\sum_{k=l}^r f(k)$，其中 $$ f(n)=\sum_{q=0}^{n-1}\sum_{k=1}^{2^n}\left[S_q([1,2,3,\dots,2^n])_k=k\right] $$

无

无

### 样例解释 以样例一中计算 $f(2)$ 为例。最初有 $2$ 叠牌，从下到上的牌都是 $[1,2,3,4]$。然后现在对第一叠牌不操作，第二叠牌洗一次，于是第二叠牌从下到上变成了 $[3,1,4,2]$。现在把两叠牌发给 $4$ 个人。第一个人拿到 $[1,3]$，第二个人拿到 $[2,1]$，第三个人拿到 $[3,4]$，第四个人拿到 $[4,2]$。发现每个人的幸运值都为 $1$（都恰好拿到了一张和自己号码相同的牌），于是幸运值总和就是 $4$，继而 $f(2)=4$。 ### 数据范围 对于全部数据，有 $1\le l\le r\le 10^{10}$。 Subtask 1（10 pts）：保证 $l=r$ 且 $r\le 12$。 Subtask 2（35 pts）：保证 $l=r$。 Subtask 3（15 pts）：保证 $1\le l\le r\le 10^6$。 Subtask 4（40 pts）：无特殊限制。