题目分析:公式很好推,到最后就是C(n-1,0)*a[n]-C(n-1,1)*a[n-1]+C(n-1,2)*a[n-2]+...+C(n-1,n-1)*a[n]。
用C(n,k)=C(n,k-1)*(n-k+1)/k即可快速得到一行的二项式系数。
我看JAVA不到1000B 15分钟就能过。。。我又敲了大数模板然后将近2个小时才过T U T......
不过大数模板敲起来还是蛮爽的。。。就是暂时不能实现大数除法以及带负数的运算(仅限非负整数)
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof a ) #define CPY( a , x ) memcpy ( a , x , sizeof a ) const int L = 10000 ; const int MAXN = 300 ; struct BigInt { int length , digit[MAXN] ; BigInt ( int number = 0 ) { CLR ( digit , 0 ) ; length = 0 ; while ( number ) { digit[length ++] = number % L ; number /= L ; } } BigInt fix () { while ( length && !digit[length - 1] ) -- length ; return *this ; } BigInt operator = ( int number ) { CLR ( digit , 0 ) ; length = 0 ; while ( number ) { digit[length ++] = number % L ; number /= L ; } return *this ; } int operator [] ( const int &index ) const { return digit[index] ; } int & operator [] ( const int &index ) { return digit[index] ; } BigInt operator + ( const BigInt &b ) const { BigInt c ; c.length = max ( length , b.length ) + 1 ; int add = 0 ; REP ( i , 0 , c.length ) { add += digit[i] + b[i] ; c[i] = add % L ; add /= L ; } return c.fix () ; } BigInt operator - ( const BigInt &b ) const { BigInt c ; c.length = max ( length , b.length ) ; int del = 0 ; REP ( i , 0 , c.length ) { del += digit[i] - b[i] ; c[i] = del ; del = 0 ; if ( c[i] < 0 ) { int tmp = ( -c[i] - 1 ) / L + 1 ; c[i] += tmp * L ; del -= tmp ; } } return c.fix () ; } BigInt operator * ( const BigInt &b ) const { BigInt c ; c.length = length + b.length ; REP ( i , 0 , length ) { int mul = 0 ; FOR ( j , 0 , b.length ) { mul += digit[i] * b[j] + c[i + j] ; c[i + j] = mul % L ; mul /= L ; } } return c.fix () ; } BigInt operator / ( const int &b ) const { BigInt c ; c.length = length ; int over = 0 ; REV ( i , length - 1 , 0 ) { over = over * L + digit[i] ; c[i] = over / b ; over %= b ; } return c.fix () ; } BigInt operator += ( const BigInt &b ) { *this = *this + b ; return *this ; } BigInt operator -= ( const BigInt &b ) { *this = *this - b ; return *this ; } BigInt operator *= ( const BigInt &b ) { *this = *this * b ; return *this ; } BigInt operator /= ( const int &b ) { *this = *this / b ; return *this ; } bool operator < ( const BigInt &b ) const { if ( length != b.length ) return length < b.length ; REV ( i , length - 1 , 0 ) if ( digit[i] != b[i] ) return digit[i] < b[i] ; return false ; } bool operator > ( const BigInt &b ) const { return b < *this ; } bool operator <= ( const BigInt &b ) const { return !( b < *this ) ; } bool operator >= ( const BigInt &b ) const { return !( *this < b ) ; } bool operator != ( const BigInt &b ) const { return b < *this || *this < b ; } bool operator == ( const BigInt &b ) const { return !( b < *this ) && !( *this < b ) ; } } ; int A[L] ; void print ( const BigInt &res ) { printf ( "%d" , res[res.length - 1] ) ; REV ( i , res.length - 2 , 0 ) printf ( "%04d" , res[i] ) ; printf ( "\n" ) ; } void solve () { int n , nn ; BigInt res = 0 , positive = 0 , negative = 0 , Cij = 1 ; scanf ( "%d" , &n ) ; REV ( i , n , 1 ) scanf ( "%d" , A + i ) ; FOR ( i , 1 , n ) { if ( i > 1 ) Cij = Cij * ( n - i + 1 ) / ( i - 1 ) ; if ( i & 1 ) positive += Cij * A[i] ; else negative += Cij * A[i] ; } //print ( positive ) ; //print ( negative ) ; if ( positive < negative ) { printf ( "-" ) ; res = negative - positive ; } else res = positive - negative ; print ( res ) ; } int main () { int T ; scanf ( "%d" , &T ) ; while ( T -- ) solve () ; return 0 ; }