首页 > 代码库 > 2014多校第六场 || HDU 4927 Series 1（杨辉三角组合数）
2014多校第六场 || HDU 4927 Series 1（杨辉三角组合数）
题目链接
题意 ： n个数，每操作一次就变成n-1个数，最后变成一个数，输出这个数，操作是指后一个数减前一个数得到的数写下来。
思路 ： 找出几个数，算得时候先不要算出来，用式子代替，例如：
1 2 3 4 5 6
(2-1) (3-2) (4-3) (5-4)(6-5)
(3-2-2+1)(4-3-3+2)(5-4-4+3)(6-5-5+4)
(4-3-3+2-3+2+2-1)(5-4-4+3-4+3+3-2)(6-5-5+4-5+4+4-3)
(5-4-4+3-4+3+3-2-4+3+3-2+3-2-2+1)(6-5-5+4-5+4+4-3-5+4+4-3+4-3-3+2)
(6-5-5+4-5+4+4-3-5+4+4-3+4-3-3+2-5+4+4-3+4-3-3+2+4-3-3+2-3+2+2-1)
把里边的数有正有负的抵消掉，得出最后的式子：
1*6-5*5+10*4-10*3+5*2-1*1
其实每个数的系数就是杨辉三角，再多写几个就能看出来，或者可以推理一下，上边的式子就像是杨辉三角的形式。
然后求出组合数即可。求的时候不要提前打表或者调用函数之类的，直接就在循环里边上减下加，要不然超时超到死啊。。。。
1 import java.io.*; 2 import java.math.*; 3 import java.text.*; 4 import java.util.*; 5 6 public class Main { 7 8 public static void main(String[] args) { 9 Scanner cin = new Scanner(System.in) ;10 BigInteger[] ch = new BigInteger[3100] ;11 BigInteger ans,a,b;12 int T ,n;13 T = cin.nextInt() ;14 while(T-- > 0)15 {16 n = cin.nextInt();17 ans = BigInteger.ZERO ;18 b = BigInteger.ONE ;19 a = BigInteger.valueOf(n-1) ;20 for(int i = 1 ; i <= n ; i++)21 ch[i] = cin.nextBigInteger();22 for(int i = 0 ; i < n ; i++)23 {24 if(i % 2 == 0)25 {26 ans = ans.add(b.multiply(ch[n-i])) ;27 }28 else 29 {30 ans = ans.subtract(b.multiply(ch[n-i])) ;31 }32 b = b.multiply(a).divide(BigInteger.valueOf(i+1)) ;33 a = a.subtract(BigInteger.ONE) ;34 }35 System.out.println(ans);36 }37 }38 39 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。