Series 1 java秒组合数

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Series 1

举几个例子发现，系数中间对称，很容易想到组合数 c(n,m)==c[n,n-m).此题就是高精度求组合数，java秒之。

time:1825ms ,接近时限，如果n还稍微大一点就超时。

 1 import java.math.*;

 2 import java.util.*;

 3 import java.io.*;

 4 import java.text.*;

 5

 6 public class Main

 7 {

 8     static int MS=3005;

 9     public static void main(String[] args)

10     {

11         Scanner cin=new Scanner(new BufferedInputStream(System.in));

12         int[] a=new int[MS];

13         int T,n;

14         T=cin.nextInt();

15         while(T-->0)

16         {

17             n=cin.nextInt();

18             for(int i=0;i<n;i++)

19                 a[i]=cin.nextInt();

20             BigInteger ans=BigInteger.valueOf(a[n-1]);

21             BigInteger res=BigInteger.ONE;

22             BigInteger flag=BigInteger.valueOf(-1);

23             BigInteger t=BigInteger.ONE;

24             n=n-1;

25             for(int i=1,j=n;i<=n;i++,j--)

26             {

27                 res=res.multiply(BigInteger.valueOf(j)).divide(BigInteger.valueOf(i));

28                 t=res.multiply(flag).multiply(BigInteger.valueOf(a[j-1]));

29                 flag=flag.multiply(BigInteger.valueOf(-1));

30                 ans=ans.add(t);

31             }

32             System.out.println(ans);

33         }

34         cin.close();

35     }

36 }