[ HDU6304 ] Chiaki Sequence Revisited

        题意:有一个数列定义如下:\(a_1 = a_2 = 1, a_n = a_{n-a_{n-1}} + a_{n-1-a_{n-2}} (n \geq 3) \),求\(\sum_{i=1}^n{a_i}\)。(\( 1 \leq n \leq 10^{18}\),多组数据,\(T \leq 10^5\))

        题解:先打个表观察一下。数列从1开始如下:1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9 10 10 11 12 12 12 13 14 14 15 16 16 16 16 16 …

可以发现这么一件事情:除了1以外,每个数的出现次数等于它二进制下从低位开始数第一个1的位置。由此我们可以得到出现次数相等的数字排列起来是一个等差数列(考虑lowbit相等的数,相邻间隔为其lowbit乘2),二分出\(a_n\)是多少,然后计算即可,时间复杂度是\(O(\log^2{n})\)的。

        有\(O(\log{n})\)的解法,依然不考虑\(a_1\)(因为\(a_1\)不满足这个性质),利用每个数出现的次数所组成的序列来看:\[1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3\ 1\ 2\ 1\ 5\ 1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3\ 1\ 2\ 1\ 6\]

仔细观察会发现这是个分形(也许),刚开始序列中只有一个数为1,之后我每次将该序列复制一遍,然后把最后一个数加1。

        第一次:\(1\ 2\)

        第二次:\(1\ 2\ 1\ 3\)

        第三次:\(1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\)

        第四次:\(1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3\ 1\ 2\ 1\ 5\)

        利用该性质,可以通过预处理出数字为\(1..2^n\)时所有数出现次数的总数以及和。由于将任意一个该序列分为两半,前后两半只有最后一位是不一样的,所以可以通过类似快速幂的方法求出答案,处理到最后多出的数字一定是相等的(具体看代码)。


page views : 3 views

发表评论

电子邮件地址不会被公开。 必填项已用*标注