hdu 4927 Series 1 （大數模板加減乘除）

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 {A₁, A₂, . . . , A_n}.

The zero-order series of A is A itself.

The first-order series of A is {B₁, B₂, . . . , B_n-1},where B_i = A_i+1 - A_i.

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 A₁, A₂, . . . , A_n. (0<=A_i<=10⁵)

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]0;i--)
				if (ans[i]>c[i])
				{
					f=1;
					break;
				}
				else if (ans[i]c[0]) f=1;
		else if (ans[0]0;i--)
			if (ans[i]>c[i])
			{
				f=1;
				break;
			}
			else if (ans[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;
}