[ 2018 Multi-University Training Contest 1 ] [ HDU6305 ] H RMQ Similar Sequence
2018 多校

[ 2018 Multi-University Training Contest 1 ] [ HDU6304 ] G Chiaki Sequence Revisited

Zarxdy34 posted @ 2018年7月24日 18:59 in HDU with tags 分形 , 70 阅读

        题意:有一个数列定义如下:\(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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter