http://acm.hdu.edu.cn/showproblem.php?pid=4927

 

【解法】：最后的结果是C(n-1,0)*a[n] －C(n-1, 1) * a[n-1] ……C(n-1,n-1)*a[1]。符号位一正一负交替。

            因为n有3000 之大，算C(n,i) 时要用到大数。

 

 

诶  其实早就把公式推出来了，就是坑在Java语言不熟悉，在编译的时候总是出现这个

 

我们一直以为是语法错误，但是又发现有什么地方写错了，卡了几个小时，人都要抓狂了。

今天拿着后面过的代码跟第一个交的比较才发现是数组里少求了一个值，所以一直提醒不能拿这个值再做运算。

好吧 Java还是够强大。虽然这次经验满不愉快的但还是长了经验啦。

 

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