hdu 4927 Series 1（组合，java大数）
浏览数：102 /
时间：2015年06月08日
http://acm.hdu.edu.cn/showproblem.php?pid=4927
比赛时分分钟推出来公式后，陷入无限的tle中。起初想处理一遍，但是3000的数量内存装不下，直接编译就不过。为了不超内存，然后又试着把三个数合并为一个，四个数合并一个，100个数合并为一个，还是TLE。。
说到底还是数学不好啊，杨辉三角的第n行的第m个数为组合数c[n-1][m-1]。
应用c[n][m] = c[n][m-1]*(n-m+1)/m，就可以快速递推出第n行的数，这样就能省去预处理的时间以及空间。
import java.io.*;
import java.util.*;
import java.math.*;
import java.math.BigInteger;
public class Main
{
public static void main(String[] args)
{
int test,n;
Scanner cin = new Scanner(System.in);
test = cin.nextInt();
while(test-- > 0)
{
n = cin.nextInt();
BigInteger [] a = new BigInteger [n+10];
BigInteger [] c = new BigInteger [n+10];
BigInteger ans = BigInteger.ZERO;
for(int i = 1; i <= n; i++)
a[i] = cin.nextBigInteger();
c[0] = BigInteger.ONE;
ans = ans.add(c[0].multiply(a[n]));
int flag = -1;
for(int i = 1; i < n; i++)
{
BigInteger t1 = BigInteger.valueOf(n).subtract(BigInteger.valueOf(i));
BigInteger t2 = BigInteger.valueOf(i);
c[i] = c[i-1].multiply(t1).divide(t2);
if(flag == -1)
ans = ans.subtract(c[i].multiply(a[n-i]));
else
ans = ans.add(c[i].multiply(a[n-i]));
flag = -flag;
}
System.out.println(ans);
}
}
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
