首页 > 代码库 > HDU 4927 Series 1 ( 组合+高精度)
HDU 4927 Series 1 ( 组合+高精度)
Series 1
大意:
题意不好翻译,英文看懂也不是很麻烦,就不翻译了。
Problem Description
Let A be an integral series {A1, A2, . . . , An}.
The zero-order series of A is A itself.
The first-order series of A is {B1, B2, . . . , Bn-1},where Bi = Ai+1 - Ai.
The ith-order series of A is the first-order series of its (i - 1)th-order series (2<=i<=n - 1).
Obviously, the (n - 1)th-order series of A is a single integer. Given A, figure out that integer.
The zero-order series of A is A itself.
The first-order series of A is {B1, B2, . . . , Bn-1},where Bi = Ai+1 - Ai.
The ith-order series of A is the first-order series of its (i - 1)th-order series (2<=i<=n - 1).
Obviously, the (n - 1)th-order series of A is a single integer. Given A, figure out that integer.
Input
The input consists of several test cases. The first line of input gives the number of test cases T (T<=10).
For each test case:
The first line contains a single integer n(1<=n<=3000), which denotes the length of series A.
The second line consists of n integers, describing A1, A2, . . . , An. (0<=Ai<=105)
For each test case:
The first line contains a single integer n(1<=n<=3000), which denotes the length of series A.
The second line consists of n integers, describing A1, A2, . . . , An. (0<=Ai<=105)
Output
For each test case, output the required integer in a line.
Sample Input
231 2 341 5 7 2
Sample Output
0-5
思路:
比赛中楠姐很快就推出来公式了,想把杨辉三角预处理出来,然后发现BigInteger大小爆内存了。。。。很无语
然后又想在暴力的基础上去优化,然后一直T到死。。。 比赛结束也没搞出来。
赛后才知道,杨辉三角是可以直接用组合公式推出来的。。。
杨辉三角的第n行的第m个数为组合数c[n-1][m-1]。
应用c[n][m] = c[n][m-1]*(n-m+1)/m,就可以快速递推出第n行的数,这样既避免了打表会出现的爆内存,也省去了暴力好多的时间。。。。。
还是太年轻 哎。。。
1 import java.io.*; 2 import java.math.*; 3 import java.util.*; 4 public class Main { 5 6 static BigInteger coe[][] = new BigInteger [3010][3010]; 7 public static void main(String[] args) throws IOException{ 8 Scanner cin = new Scanner(System.in); 9 BigInteger []a = new BigInteger[3010]; 10 BigInteger []c = new BigInteger[3010]; 11 int T;12 T = cin.nextInt();13 while(T-- > 0){14 int n;15 n = cin.nextInt();16 for(int i = 1; i <= n; ++i){17 a[i] = cin.nextBigInteger();18 }19 BigInteger ans = BigInteger.ZERO;20 c[0] = BigInteger.ONE;21 ans = ans.add(c[0].multiply(a[n]));22 int t = -1;23 for(int i = 1; i < n; ++i){24 BigInteger t1 = BigInteger.valueOf(n).subtract(BigInteger.valueOf(i)); 25 BigInteger t2 = BigInteger.valueOf(i);26 c[i] = c[i-1].multiply(t1).divide(t2); 27 ans = ans.add(c[i].multiply(a[n-i]).multiply(BigInteger.valueOf(t)));28 t *= -1; 29 }30 System.out.println(ans);31 }32 33 }34 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。