hdu 5587 规律

题意：开始序列{1};

一次变换{1，1，2}；
两次变换{1，1，2，1，2，2，3}
。。。
求s[n];
题解：打表 S1，S2，S4，S8，S16，S32。。。。。。
公式 S[n]=S[最近的比其小的2的？次方]+S[n-最近的比其小的2的？次方]+n-n-最近的比其小的2的？次方;
复杂度log（n）；

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

using namespace std;

#define ll __int64

int scan()

{

    int res =  , ch ;

    while( !( ( ch = getchar() ) >= '' && ch <= '' ) )

    {

        if( ch == EOF )  return  <<  ;

    }

    res = ch - '' ;

    while( ( ch = getchar() ) >= '' && ch <= '' )

        res = res *  + ( ch - '' ) ;

    return res ;

}

ll a[];

ll pow1(ll x, ll y)

{

    ll num=;

    for(ll i=;i<y;i++)

    {

        num*=x;

    }

    return num;

}

ll hehe(ll x)

{

    a[]=;

    a[]=;

    ll i,sum=;

    for(i=;i<=x;i++)

    {

        a[i]=sum+pow1(,i)-i;

        sum+=a[i];

    }

    return a[x];

}

ll erfen(ll x)

{

    ll i;

    if(x==)

        return ;

    if(x==)

        return ;

    ll num=;

    for(i=;;i++)

    {

        num*=;

        if(num>=x)

            break;

    }

    if(num==x)

    return hehe(i);

    else

    return erfen(num/)+erfen(x-num/)+x-num/;

}

int main()

{

    ll x,y,z,i,t;

    scanf("%I64d",&x);

    while(x--)

    {

        scanf("%I64d",&y);

        printf("%I64d\n",erfen(y));

    }

    return ;

}