本文主要是介绍【HDU】4927 Series 1 高精度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
传送门:【HDU】4927 Series 1
题目分析:公式很好推,到最后就是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] ;elsenegative += Cij * A[i] ;}//print ( positive ) ;//print ( negative ) ;if ( positive < negative ) {printf ( "-" ) ;res = negative - positive ;}elseres = positive - negative ;print ( res ) ;
}int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- )solve () ;return 0 ;
}
这篇关于【HDU】4927 Series 1 高精度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!