hdu4927 大数

题意：给一个数列，进行n - 1次操作，每次操作是把数列的相邻的两个数的后一个减前一个，求经过操作最后的数的值。

思路:虽然数据只有3000，暴力n ^ 2不会超时，但是因为加减很多，会出现数非常大的情况，所以要用大数，

???? 只是用大数加n ^ 2的模拟的话也超时了；

?? 那就得找规律，发现会出现一个杨辉三角，即 a[n],a[n - 1],a[n - 2],……,a[1]的系数分别为C(n - 1,0),C(n - 1,1),…… ，C(n - 1,n - 1)，这样就能写了。

import java.io.*;  
import java.math.*;  
import java.util.*;  


public class Main  
{  
    public static void main(String args[])  
    {  
        Scanner in = new Scanner(System.in);
        int Tcase = in.nextInt();
        for(int ii = 1; ii <= Tcase; ii ++)
        {
            BigInteger a[] = new BigInteger[3005];
            int n = in.nextInt();
            for(int i = 1; i <= n; i ++)
                a[i] = in.nextBigInteger();
            BigInteger temp=BigInteger.valueOf(1);
            
            BigInteger ans=BigInteger.valueOf(0);
            for(int i = 1; i <= n; i ++)
            {
                ans = ans.add(temp.multiply(a[i]));
                System.out.println(temp+"    "+a[i] + "   " +  temp.multiply(a[i]));
                temp = temp.multiply(BigInteger.valueOf(-(n - i))).divide(BigInteger.valueOf(i)) ;
            }
            System.out.println(ans);
        }
         
    }  
}