[ 2018 Multi-University Training Contest 1 ] [ HDU6304 ] G 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\)时所有数出现次数的总数以及和。由于将任意一个该序列分为两半，前后两半只有最后一位是不一样的，所以可以通过类似快速幂的方法求出答案，处理到最后多出的数字一定是相等的（具体看代码）。

#include <bits/stdc++.h>
using namespace std;
const int mo=1e9+7;

long long Pow(long long x,int p)
{
    long long res=1;
    while (p)
    {
        if (p&1) (res*=x)%=mo;
        (x*=x)%=mo;
        p>>=1;
    }
    return res;
}

long long Mul(long long a,long long b)
{
    return (a%mo)*(b%mo)%mo;
}

long long c[64];
long long sum[64];
long long n;

long long Solve(long long x)
{
    long long ans=1,num=0;
	x--;
    for (int i=62;i>=0;i--) if (x>=c[i])
    {
        x-=c[i];
        ans=(ans+sum[i]+Mul(c[i],num))%mo;
        num+=(1ll<<i);
    }
    (ans+=Mul(x,num+1))%=mo;
    return ans;
}

int main()
{
    c[0]=1;c[1]=3;
    sum[0]=1;sum[1]=5;
    for (int i=2;i<63;i++) c[i]=c[i-1]*2+1,sum[i]=(2*sum[i-1]+Pow(2,i)+Pow(2,i-1)*(Pow(2,i)-1))%mo;
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld",&n);
        printf("%lld\n",Solve(n));
    }
	return 0;
}