HDU 4927 Series 1
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.
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)
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
题意：求最后合并的数是多少
思路：JAVA高精度，推出来后发现是系数是杨辉三角。处理出系数后计算结果
import java.math.BigInteger;
import java.util.*;
import java.io.*;
/**
* Created by acer on 14-8-7.
*/
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int t, n;
t = cin.nextInt();
while (t != 0) {
t--;
n = cin.nextInt();
BigInteger arr[] = new BigInteger[n];
for (int i = 0; i < n; i++) {
arr[i] = cin.nextBigInteger();
}
if (n == 1) {
System.out.println(arr[0]);
continue;
}
BigInteger ans = new BigInteger("0");
BigInteger C[] = new BigInteger[n + 2];
BigInteger t1 = new BigInteger("0");
BigInteger t2 = new BigInteger("0");
C[0] = BigInteger.valueOf(1);
for (int i = 1; i < n; i++) {
t1 = BigInteger.valueOf(n-i);
t2 = BigInteger.valueOf(i);
C[i] = C[i-1].multiply(t1).divide(t2);
}
int flag = 1;
for (int i = n - 1; i >= 0; i--) {
if (flag == -1)
ans = ans.subtract(arr[i].multiply(C[i]));
else ans = ans.add(arr[i].multiply(C[i]));
flag *= -1;
}
System.out.println(ans);
}
}
}