Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不用递推,只是大数问题

Posted by HH_YT at 2012-09-20 14:36:00 on Problem 1090
#include<stdio.h>
#include<string.h>
int array[1001];
int res[1001];
int ini()
{
	int z,flag=0;
	for(z=1;z<=1000;z++)
	{
		res[z]+=flag;
		flag=res[z]/10;
		res[z]%=10;
	}
	return 0;
}
int p(int a,int b)
{
	int r[1001],i,j,z,flag,rnum=1;
	memset(r,0,sizeof(r));
	r[1]=1;
	for(i=1;i<=b;i++)
	{
		for(j=1;j<=rnum;j++)
		{
			r[j]*=a;
		}
		flag=0;
		for(z=1;z<=rnum;z++)
		{
			r[z]+=flag;
			flag=r[z]/10;
			r[z]%=10;
		}
		while(flag!=0)
		{
			r[++rnum]=flag%10;
			flag/=10;
		}
	}
	for(i=1;i<=rnum;i++)
	{
		res[i]+=r[i];
	}
	return ini();
}
int add(int num)
{
	res[1]+=num;
	return ini();
}
int dfs(int n,int* flag)
{
	int flag1[1001];
	if(n==1)
		if(flag[n]!=array[n])
			return add(1);
		else
			return add(0);
	if(array[n]==flag[n])
		return dfs(n-1,flag);
	else
	{
		memset(flag1,0,sizeof(flag1));
		flag1[n-1]=1;
		return dfs(n-1,flag1)+p(2,n-1);
	}
	return 0;
}
int main()
{
	int i;
	int n,flag[1001];
	while(scanf("%d",&n)!=EOF)
	{
		memset(flag,0,sizeof(flag));
		memset(res,0,sizeof(res));
		for(i=1;i<=n;i++)
			scanf("%d",&array[i]);
		dfs(n,flag);
		int xx=0;
		for(i=1000;i>=1;i--)
		{
			if(xx==0&&res[i]==0)
				continue;
			xx=1;
			printf("%d",res[i]);
		}
		if(xx==0)
			printf("0");
		printf("\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator