BZOJ 2656: [Zjoi2012]数列(sequence)

小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式：

小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数 N，小白则说出 的值，如果当 N 很大时小白仍能很快的说出正确答案，这就说明小白的确得到了公式。但这个方法有一个很大的漏洞：小蓝自己不会做，没法验证小白的答案是否正确。作为小蓝的好友，你能帮帮小蓝吗？

Input

输入文件第一行有且只有一个正整数 T，表示测试数据的组数。 第 2 ～ T+1 行，每行一个非负整数 N。

Output

输出文件共包含 T 行。 第 i 行应包含一个不含多余前缀 0 的数，它的值应等于 An(n 为输入数据中第 i+1 行被读入的整数)

Sample Input

3
1
3
10

Sample Output

1
2
3

HINT

T<=20,N<=10^100

Solution

首先手推几个较小的值，可以发现当 $i$ 为奇数时，递归算几次 $A(i)$，会产生一些相同的值，那么直接记忆化就行了。
至于证明，我也不会（从二进制的角度考虑的话，似乎大概就 $\log n$ 种值）

Code

#include<cstdio>
#include<cstring>
#include<tr1/unordered_map>

#define bas 1000000000
#define rep(a,b) if(a<(b))a=(b)

struct hjd
{
    int a[20],len;
    hjd(){
        len=0;
        memset(a,0,sizeof(a));
    }
    hjd(const hjd &x)
    {
        len=x.len;
        memset(a,0,sizeof(a));
        for(int i=0;i<len;i++)a[i]=x.a[i];
    }
    hjd(int x){
        len=1;
        memset(a,0,sizeof(a));
        a[0]=x;
    }
    bool operator ==(const hjd &x)const
    {
        if(len^x.len)return 0;
        for(int i=0;i<len;i++)
            if(a[i]^x.a[i])return 0;
        return 1;
    }
    inline void div2()
    {
        for(int i=len-1;i>0;i--)
        {
            if(a[i]&1)a[i-1]+=bas;
            a[i]>>=1;
        }
        a[0]>>=1;
        if(!a[len-1])len--;
    }
    inline void plus(const hjd &x)
    {
        rep(len,x.len);
        for(int i=0;i<len;i++)
        {
            a[i]+=x.a[i];
            if(a[i]>bas)a[i]-=bas,a[i+1]++;
        }
        if(a[len])len++;
    }
    inline void print()
    {
        printf("%d",a[len-1]);
        for(int i=len-2;i>=0;i--)
            printf("%09d",a[i]);
        printf("\n");
    }
};

struct hjd_hash
{
    size_t operator ()(const hjd &x)const//乱搞哈希
    {
        int ans=0;
        for(int i=0;i<x.len;i++)
            ans^=x.a[i];
        return ans;
    }
};

std::tr1::unordered_map<hjd,hjd,hjd_hash> s;
int aaa=0;
hjd calc(hjd x)
{
    hjd ret;
    if(!x.len)return ret;
    while((~x.a[0]&1)&&(x.len!=1||x.a[0]!=1))x.div2();//除去2
    if(s.find(x)!=s.end())return s[x];//记忆化
    hjd y=x;
    x.div2();
    ret=calc(x);
    x.plus(1);
    ret.plus(calc(x));//计算A(x)
    s[y]=ret;
    return ret;
}

char buf[200];

int main()
{
    s[1]=1;
    int T,n,uu[9],y=1;
    for(int i=0;i<9;i++)
        uu[i]=y,y*=10;
    scanf("%d",&T);
    while(T--)
    {
        s.clear();
        s[1]=1;
        scanf("%s",buf);
        n=strlen(buf);
        hjd tmp;
        for(int i=n-1,j=0,ll=1;i>=0;i--)//输入，倒序
        {
            tmp.len=ll;
            tmp.a[ll-1]+=(buf[i]-'0')*uu[j];
            j++;
            if(j==9)j=0,ll++;
        }
        hjd t2=calc(tmp);
        if(!t2.len)
            printf("0\n");
        else
        {
            t2.print();
        }
    }
}

日期： 2016-10-21

标签： BZOJ 高精度 乱搞

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/57/ 查看。