BZOJ 2656: [Zjoi2012]数列(sequence)

###Description
小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式：
![1.jpg][1]
小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数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)，会产生一些相同的值
那么直接记忆化就行了
至于证明，我也不会（从二进制的角度考虑的话，似乎大概就logn种值）

###Code
```c++
#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();
		}
	}
}
```

[1]: /usr/uploads/2016/10/1978638953.jpg

BZOJ 2656: [Zjoi2012]数列(sequence)

最新文章

最近回复

分类

归档

其它