题面

定义一个序列 $a$ ：

$$a_n = \begin{cases} 1 & n = 1, 2 \\ a_{n - a_{n - 1}} + a_{n - 1 - a_{n - 2}} & n \ge 3 \end{cases}$$

记序列 $a$ 的前缀和 $s_i = \sum\limits_{k = 1}^{i} a_k$ 。现共有 $T$ 组数据，每组数据给定 $k$ ，试求 $s_k$ 对 $10^9 + 7$ 取模后的值。

数据范围：

$1 \le T \le 10^5$

$1 \le n \le 10^{18}$

题目链接

分析

我们先对 $a_i$ 打个表吧（逃

前 10000 个值

我们观察这些值，不难发现从第 $2$ 个值开始，$1$ 出现了 $1$ 次，$2$ 出现了 $2$ 次，$3$ 出现了 $1$ 次，$4$ 出现了 $3$ 次…… 好像所有奇数值只会出现 $1$ 次，而能被 $2$ 整除但不能被 $4$ 整除的都出现 $2$ 次，能被 $4$ 整除但不能被 $8$ 整除的都出现 $3$ 次…… 如果我们结合每个数的二进制再观察一番就会发现，除 $1$ 以外每个数 $i$ 的出现次数 $f(i)$ 都满足：

$$f(i) = \log_{2}({\text{lowbit}(i))} + 1$$

如果你不理解上面这个式子，你大可不必管它。你只需要知道：对于能被 $2^i$ 整除但不能被 $2^{i + 1}$ 整除的数 $i$ ，其 $f(i) = i + 1$ 。也就是说，$f(i)$ 的值即 $i$ 中含有质因子 $2$ 的最大次数加 $1$ 。

为了处理 $1$ 这一特例，我们不妨把 $a_1$ 扔掉，然后把 $a_i$ 看作 $a_{i - 1}$ 。最后再在答案上加 $1$ 。

现在我们不妨把出现了 $f(i)$ 次的 $i$ 都看成一个长度为 $f(i)$ 的块。直观地说，就是把原序列这样划分：

$$[1],\ [2, 2], \ [3], \ [4, 4, 4], \ [5], \ [6,6], \ [7], \ [8, 8, 8], \ \dots$$

那么前 $k$ 个数里面应该会有 $t$ 个这样完整的块，另外最后可能还有一个不完整的块。我们需要求的 $s_k$ ，也就是前面完整块的和，再加上最后一个不完整块的和（如果有的话）。

前 $t$ 个完整块的和：

$$\sum\limits_{i = 1}^{t} (i \cdot f(i))$$

前 $t$ 个完整块一共包含数的个数：

$$\sum\limits_{i = 1}^{t} f(i)$$

所以剩余数的个数：

$$k - \sum\limits_{i = 1}^{t} f(i)$$

我们知道这个剩余的不完整的块中所有的数都是 $t + 1$ ，所以不完整块的和：

$$(t + 1) \cdot (k - \sum\limits_{i = 1}^{t} f(i))$$

加起来便有：

$$s_k = \sum\limits_{i = 1}^{t} (i \cdot f(i)) + (t + 1) \cdot (k - \sum_{i = 1}^{t} f(i))$$

如何确定 $t$ 的值呢？我们可以考虑二分答案把求解转为判定。

再次温习一遍 $f(i)$ 的规律：对于能被 $2^i$ 整除但不能被 $2^{i + 1}$ 整除的数 $i$ ，有 $f(i) = i + 1$ 。

于是我们不难得出：

$$\sum\limits_{i = 1}^{t} f(i) = \lfloor \frac{t}{2^0} \rfloor + \lfloor \frac{t}{2^1} \rfloor + \lfloor \frac{t}{2^2} \rfloor + \dots$$

我们不妨把 $f$ 想象成一堆桶。刚开始时对于所有数都有 $f(i) = 0$ 。在上面的式子中，$\lfloor \frac{t}{2^0} \rfloor$ 相当于给所有能被 $2^0$ 数的 $f$ 都加了 $1$ ，$\lfloor \frac{t}{2^1} \rfloor$ 相当于给所有能被 $2^1$ 整除的数的 $f$ 都加了 $1$ ，…… 也就是说，能被 $2^i$ 整除但不能被 $2^{i + 1}$ 整除的数的 $f$ 都被加了 $i + 1$ 次 $1$ 。

另外二分时要注意两点：

• 不可以直接用等比数列求和公式，因为每一项都向下取整了；
• 关于答案范围：通过前面的表可以观察到 $t$ 的值一般在 $\frac{k}{2}$ 左右，且很多时候略大于 $\frac{k}{2}$ ，故为了卡进时限可以将二分范围确立为 $[\frac{k}{2} - 1, \frac{k}{2} + 50]$ 。

至于前 $t$ 个完整块的求和，我们不难发现如下规律：

• 出现次数为 $1$ 的数：$1, \ 3, \ 5, \ 7, \ 9, \ \dots$ 是个首项为 $2^0$ ，公差为 $2^1$ 的等差数列。
• 出现次数为 $2$ 的数：$2, \ 6, \ 10, \ 14, \ 18, \ \dots$ 进一步，可化为：$2^1 \times (1, \ 3, \ 5, \ 7, \ 9, \ \dots)$
• 出现次数为 $3$ 的数：$4, \ 12, \ 20, \ 28, \ 36, \ \dots$ 进一步，可化为：$2^2 \times (1, \ 3, \ 5, \ 7, \ 9, \ \dots)$
• $\dots$
• 出现次数为 $i$ 的数：$2^{i - 1} \times (1, \ 3, \ 5, \ 7, \ 9, \ \dots)$

所以我们用等差数列求和公式即可得解。

至此，关键问题就都解决了。

实现

完整参考代码

%%%

• wyj_alone_smile - HDU 6304（找规律）
• purple_bro - HDU - 6304 Chiaki Sequence Revisited