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
1, A
2, . . . , A
n}.
The zero-order series of A is A itself.
The first-order series of A is {B
1, B
2, . . . , 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
1, A
2, . . . , A
n. (0<=A
i<=10
5)
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; }