题目链接

题意 : 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

其实每个数的系数就是杨辉三角,再多写几个就能看出来,或者可以推理一下,上边的式子就像是杨辉三角的形式。

然后求出组合数即可。求的时候不要提前打表或者调用函数之类的,直接就在循环里边上减下加,要不然超时超到死啊。。。。

 import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*; public class Main { public static void main(String[] args) {
Scanner cin = new Scanner(System.in) ;
BigInteger[] ch = new BigInteger[3100] ;
BigInteger ans,a,b;
int T ,n;
T = cin.nextInt() ;
while(T-- > 0)
{
n = cin.nextInt();
ans = BigInteger.ZERO ;
b = BigInteger.ONE ;
a = BigInteger.valueOf(n-1) ;
for(int i = 1 ; i <= n ; i++)
ch[i] = cin.nextBigInteger();
for(int i = 0 ; i < n ; i++)
{
if(i % 2 == 0)
{
ans = ans.add(b.multiply(ch[n-i])) ;
}
else
{
ans = ans.subtract(b.multiply(ch[n-i])) ;
}
b = b.multiply(a).divide(BigInteger.valueOf(i+1)) ;
a = a.subtract(BigInteger.ONE) ;
}
System.out.println(ans);
}
} }
05-07 15:19