2656: [Zjoi2012]数列(sequence)（递归+高精度）

　　好久没写题了T T NOIP 期中考双血崩

　　显然f(x)=f(x>>1)+f((x>>1)+1)，考虑每次往x>>1递归，求出f(x)，复杂度O(logN)

　　我们设f(x>>1)的值为ansa[x]，f((x>>1)+1)的值为ansb[x]

　　如果x>>1为偶数，ansa[x]=ansa[x>>1]，ansb[x]=ansa[x>>1]+ansb[x>>1]

　　如果x>>1为奇数，ansa[x]=ansa[x>>1]+ansb[x>>1]，ansb[x]=ansb[x>>1]

　　随便举个例子很好理解的，高精度写起来比较麻烦T T

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int base=1e9, bit=;

int T;

char s[];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

struct tjmll

{

    int sum[], f;

    tjmll(){f=; memset(sum, , sizeof(sum));}

    tjmll operator= (ll x)

    {

        memset(sum, , sizeof(sum));

        while(x)

        {

            sum[++sum[]]=x%base;

            x/=base;

        }

        return *this;

    }

} ansa, ansb, n;

void print(const tjmll &a)

{

    if(a.f==-) putchar('-');

    printf("%d", a.sum[a.sum[]]);

    for(int i=a.sum[]-;i>=;i--) printf("%0*d", bit, a.sum[i]);

}

tjmll operator+(const tjmll &a, const tjmll &b)

{

    tjmll tmp; tmp.sum[]=max(a.sum[], b.sum[]);

    for(int i=;i<=tmp.sum[];i++)

    {

        tmp.sum[i]+=a.sum[i]+b.sum[i];

        tmp.sum[i+]+=tmp.sum[i]/base;

        tmp.sum[i]%=base;

    }

    if(tmp.sum[tmp.sum[]+]) tmp.sum[]++;

    return tmp;

}

inline void div2(tjmll &x)

{

    int pre=;

    for(int i=x.sum[];i;i--)

    {

        int tmp=pre*base+x.sum[i];

        x.sum[i]=tmp>>;

        pre=tmp&;

    }

    if(!x.sum[x.sum[]]) x.sum[]--;

}

inline void dfs(tjmll x)

{

    if(x.sum[]==) return;

    if(x.sum[]== && x.sum[]==) ansa=, ansb=;

    tjmll now; now=now+x;

    div2(x); dfs(x);

    if(now.sum[]&) ansa=ansa+ansb;

        else ansb=ansa+ansb;

}

int main()

{

    read(T);

    while(T--)

    {

        scanf("%s", s+); n=; int len=strlen(s+), now=;

        for(int i=len;i;i--)

        {

            if((len-i)%bit==) ++n.sum[], now=;

            n.sum[n.sum[]]+=(s[i]-'')*now; now*=;

        }

        ansa=; ansb=; dfs(n); print(ansa); puts("");

    }

    return ;

}