HDUOJ 6304 - Chiaki Sequence Revisited

题面

定义一个序列 aa

an={1n=1,2anan1+an1an2n3a_n =
\begin{cases}
1 & n = 1, 2 \
a_{n - a_{n - 1}} + a_{n - 1 - a_{n - 2}} & n \ge 3
\end{cases}

记序列 aa 的前缀和 si=k=1iaks_i = \sum\limits_{k = 1}^{i} a_k。现共有 TT 组数据,每组数据给定 kk,试求 sks_k109+710^9 + 7 取模后的值。

数据范围

1T1051 \le T \le 10^5

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

题目链接

分析

我们先对 aia_i 打个表吧(逃

前 10000 个值

我们观察这些值,不难发现从第 22 个值开始,11 出现了 11 次,22 出现了 22 次,33 出现了 11 次,44 出现了 33 次…… 好像所有奇数值只会出现 11 次,而能被 22 整除但不能被 44 整除的都出现 22 次,能被 44 整除但不能被 88 整除的都出现 33 次…… 如果我们结合每个数的二进制再观察一番就会发现,除 11 以外每个数 ii 的出现次数 f(i)f(i) 都满足:

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

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

为了处理 11 这一特例,我们不妨把 a1a_1 扔掉,然后把 aia_i 看作 ai1a_{i - 1}。最后再在答案上加 11


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

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

那么前 kk 个数里面应该会有 tt 个这样完整的块,另外最后可能还有一个不完整的块。我们需要求的 sks_k,也就是前面完整块的和,再加上最后一个不完整块的和(如果有的话)。

tt 个完整块的和:

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

tt 个完整块一共包含数的个数:

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

所以剩余数的个数:

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

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

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

加起来便有:

sk=i=1t(if(i))+(t+1)(ki=1tf(i))s_k = \sum\limits_{i = 1}^{t} (i \cdot f(i)) + (t + 1) \cdot (k - \sum_{i = 1}^{t} f(i))


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

再次温习一遍 f(i)f(i) 的规律:对于能被 2i2^i 整除但不能被 2i+12^{i + 1} 整除的数 ii,有 f(i)=i+1f(i) = i + 1

于是我们不难得出:

i=1tf(i)=t20+t21+t22+\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

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

另外二分时要注意两点:

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

至于前 tt 个完整块的求和,我们不难发现如下规律:

  • 出现次数为 11 的数:1, 3, 5, 7, 9, 1, \ 3, \ 5, \ 7, \ 9, \ \dots 是个首项为 202^0,公差为 212^1 的等差数列。
  • 出现次数为 22 的数:2, 6, 10, 14, 18, 2, \ 6, \ 10, \ 14, \ 18, \ \dots 进一步,可化为:21×(1, 3, 5, 7, 9, )2^1 \times (1, \ 3, \ 5, \ 7, \ 9, \ \dots)
  • 出现次数为 33 的数:4, 12, 20, 28, 36, 4, \ 12, \ 20, \ 28, \ 36, \ \dots 进一步,可化为:22×(1, 3, 5, 7, 9, )2^2 \times (1, \ 3, \ 5, \ 7, \ 9, \ \dots)
  • \dots
  • 出现次数为 ii 的数:2i1×(1, 3, 5, 7, 9, )2^{i - 1} \times (1, \ 3, \ 5, \ 7, \ 9, \ \dots)

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


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

实现

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/07/24/hduoj-6304/