首页 > 代码库 > hdu 4927 Series 1 （大数模板加减乘除）

hdu 4927 Series 1 （大数模板加减乘除）

2024-07-19 03:06:31   219人阅读

Series 1

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1067    Accepted Submission(s): 390


Problem Description
Let A be an integral series {A1, A2, . . . , An}.

The zero-order series of A is A itself.

The first-order series of A is {B1, B2, . . . , Bn-1},where Bi = Ai+1 - Ai.

The ith-order series of A is the first-order series of its (i - 1)th-order series (2<=i<=n - 1).

Obviously, the (n - 1)th-order series of A is a single integer. Given A, figure out that integer.
 

Input
The input consists of several test cases. The first line of input gives the number of test cases T (T<=10).

For each test case:
The first line contains a single integer n(1<=n<=3000), which denotes the length of series A.
The second line consists of n integers, describing A1, A2, . . . , An. (0<=Ai<=105)
 

Output
For each test case, output the required integer in a line.
 

Sample Input
2
3
1 2 3
4
1 5 7 2
 

Sample Output
0
-5
 

Author
BUPT
 

Source
2014 Multi-University Training Contest 6

由题意容易发现规律，即系数为二项式展开：C (n,n-1)=C(n,n)*n/1; C(n,n-2)=C(n,n-1)*(n-1)/2;


#include"stdio.h"
#include"string.h"
#include"iostream"
#include"algorithm"
using namespace std;
#define LL __int64
#define N 300
#define M 100000000000
#define max(a,b) (a>b?a:b)
int a[3010];
LL c[N],ans[N],cc[N];  //数组大小，数组第一个元素存大数的长度，若长度为负数则代表大数小于零
void mul(LL*c,int x)      //一个大数乘以一个整数
{
    int i;
	for(i=1;i<=c[0];i++)
		c[i]=c[i]*x;
	for ( i=1;i<=c[0];i++)
	{
		c[i+1]+=c[i]/M;
		c[i]=c[i]%M;
	}
	while(c[c[0]+1])
	{
		c[0]++;
		c[c[0]+1]=c[c[0]]/M;
		c[c[0]]%=M;
	}
}
void div(LL *c,int y)  //一个大数除以一个整数
{
    int i;
	for ( i=c[0];i>1;i--)
	{
		c[i-1]+=(c[i]%y)*M;
		c[i]/=y;
	}
	c[1]/=y;
	while (c[c[0]]==0) c[0]--;
}
void add(LL *ans,LL *c)    //一个大数加上一个大数，结果存入ans
{
	int f=-1,i;
	if (ans[0]<0)
	{
		if (-ans[0]>c[0]) f=1;
		else if (-ans[0]<c[0]) f=0;
		else
		{
			for (i=c[0];i>0;i--)
				if (ans[i]>c[i])
				{
					f=1;
					break;
				}
				else if (ans[i]<c[i])
				{
					f=0;
					break;
				}
			if (i==0)
			{
			    for(i=0;i<N;i++)
                    ans[i]=0;
				ans[0]=1;
				return;
			}
		}
	}
	else
	{
		int l=max(ans[0],c[0]);
		for(i=1;i<=l;i++)
		{
			ans[i+1]+=(ans[i]+c[i])/M;
			ans[i]=(ans[i]+c[i])%M;
		}
		while(ans[ans[0]+1])
		{
			ans[0]++;
			ans[ans[0]+1]+=ans[ans[0]]/M;
			ans[ans[0]]%=M;
		}
		return;
	}
	if(f!=-1)
	{
		if(f)
		{
			for(i=1;i<=-ans[0];i++)
			{
				ans[i]-=c[i];
				if (ans[i]<0)
				{
					ans[i]+=M;
					ans[i+1]-=1;
				}
			}
			while(ans[-ans[0]]==0) ans[0]++;
		}
		else
		{
			for(i=1;i<=c[0];i++)
			{
				ans[i]=c[i]-ans[i];
				if(ans[i]<0)
				{
					ans[i]+=M;
					c[i+1]--;
				}
			}
			ans[0]=c[0];
			while(ans[ans[0]]==0) ans[0]--;
		}
	}
}
void sub(LL *ans,LL *c)  //一个大数减去一个大数，结果存入ans
{
	int i;
	if (ans[0]<0)
	{
		int l=max(-ans[0],c[0]);
		for (i=1;i<=l;i++)
		{
			ans[i+1]+=(ans[i]+c[i])/M;
			ans[i]=(ans[i]+c[i])%M;
		}
		while (ans[-ans[0]+1])
		{
			ans[0]--;
			ans[-ans[0]+1]+=ans[-ans[0]]/M;
			ans[-ans[0]]%=M;
		}
	}
	else
	{
		int f=0;
		if (ans[0]>c[0]) f=1;
		else if (ans[0]<c[0]) f=0;
		else
		{
			for (i=ans[0];i>0;i--)
			if (ans[i]>c[i])
			{
				f=1;
				break;
			}
			else if (ans[i]<c[i])
			{
				f=0;
				break;
			}
			if (i==0)
			{
				for(i=0;i<N;i++)
                    ans[i]=0;
				ans[0]=1;
				return;
			}
		}
		if (f)
		{
			for (i=1;i<=ans[0];i++)
			{
				ans[i]-=c[i];
				if (ans[i]<0)
				{
					ans[i+1]--;
					ans[i]+=M;
				}
			}
			while (ans[ans[0]]==0) ans[0]--;
		}
		else
		{
			for (i=1;i<=c[0];i++)
			{
				ans[i]=c[i]-ans[i];
				if (ans[i]<0)
				{
					ans[i]+=M;
					c[i+1]--;
				}
			}
			ans[0]=-c[0];
			while (ans[-ans[0]]==0) ans[0]++;
		}
	}
}
int main()
{
	int T,n,i;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		for (i=0;i<n;i++)
			scanf("%d",&a[i]);
		memset(c,0,sizeof(c));
		memset(ans,0,sizeof(ans));
		c[0]=c[1]=1;
		ans[0]=0;
		int flag=1;
		if(n%2==0)
            flag=-1;
		for(i=0;i<n;i++)
        {
            if(i>0)
            {
                mul(c,n-i);
                div(c,i);
            }
            memcpy(cc,c,sizeof(c));
            mul(c,a[i]);
            if(flag==1)
                add(ans,c);
            else
                sub(ans,c);
            flag*=-1;
            memcpy(c,cc,sizeof(cc));
        }
		if (ans[0]<0)
		{
			printf("-");
			ans[0]=-ans[0];
		}
		printf("%I64d",ans[ans[0]]);
		for (i=ans[0]-1;i>0;i--)
			printf("%011I64d",ans[i]);
		printf("\n");
	}
	return 0;
}





hdu 4927 Series 1 （大数模板加减乘除）


联系
我们