首页 > 代码库 > HDU 4927 Series 1(高精度+杨辉三角)

HDU 4927 Series 1(高精度+杨辉三角)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4927

解题报告:对于n,结果如下:

C(0,n-1) *A[n] - C(1,n-1) * A[n-1] + C(2,n-1) * A[n-2] - C(3,n-1) * A[n-3] ....... C(n-1,n-1) * A[1];

n <= 3000,到了后面二项式会很大,因为要用到高精度的乘法和除法,所以直接用java的大数类写了,简单多了。

 1 import java.math.BigInteger; 2 import java.util.*; 3  4 public class Main  5 { 6     public static BigInteger ans,a,b,flag,temp;  7     public static BigInteger[] A = new BigInteger[3005]; 8     public static void main(String[] argv) 9     {10         11         Scanner input = new Scanner(System.in);12         int T,n;13         T = input.nextInt();14         for(int t = 0;t < T;++t)15         {16             n = input.nextInt();17             ans = ans.valueOf(0);18             a = a.valueOf(1);19             b = a;20             for(int i = 1;i <= n;++i)21             {22                 A[i] = input.nextBigInteger();23                 A[i] = A[i].multiply(a);24                 a = a.multiply(a.valueOf(n-i));25                 a = a.divide(a.valueOf(i));26             }27             flag = flag.valueOf(1);28             for(int i = n;i >= 1;--i)29             {30                 A[i] = A[i].multiply(flag);31                 ans = ans.add(A[i]);32                 flag = flag.multiply(flag.valueOf(-1));33             }34             System.out.println(ans);35         }36     }37 }
View Code