首页 > 代码库 > HDU4927 Series 1 高精度

HDU4927 Series 1 高精度

题意:一个数列每一次将它变为  bi = ai+1 - ai    最后数组变为一个数,问你这个数答案为多少。

解题思路:最开始以为这个数一定是在int范围以内的,但是推出了公式就不湿了  公式应该是  C(n,0)*a[n] - C(n,1)*a[n-1] + C(n,2)*a[n-2] ....一直到 a[1],

可以知道这个题系数是二项分布,所以直接用JAVA大数类 a掉的,java大数类有个很恶心的性质,数越大,操作越慢,所以要避免这个情况

解题代码:

 1 import java.math.BigInteger; 2 import java.util.Scanner; 3 import java.io.*; 4  5 public class Main { 6     public static void main(String[] args) { 7         Scanner cin = new Scanner(System.in); 8             int t,n; 9             BigInteger[] a = new BigInteger[3004];10             BigInteger[] b = new BigInteger[3004];11         //    BigInteger[][] c = new BigInteger[3004][1500];12             b[0] = BigInteger.valueOf(1);13             t=cin.nextInt();14             while(t > 0)15             {16               t--;17               BigInteger  ans = BigInteger.valueOf(0);18               n = cin.nextInt();19               for(int i = 1;i <= n-1;i ++)20               {21                   b[i] = b[i-1].multiply(BigInteger.valueOf(n-i));22                   b[i] = b[i].divide(BigInteger.valueOf(i));23               }24               int j = 0;25               if(n % 2 == 0)26                   j = 1;27               for(int i = 1;i <= n;i ++,j++)28               {29                  a[i] = cin.nextBigInteger();30                 //a[i].multiply(b[n-1].divide(b[i-1].multiply(b[n-i])));31                  a[i] = a[i].multiply(b[i-1]);32                  if(j % 2 == 0 )33                    ans = ans.add(a[i]);34                  else ans = ans.subtract(a[i]);35                 // System.out.println(a[i]);36               37             }38           System.out.println(ans); 39         }40     }41 }
View Code