【HDU - 4927】Series 1

BUPT2017 wintertraining(15) #5I

题意

输出序列A[1..n]的第n-1阶差分（一个整数）。

题解

观察可知答案就是

[sum_{i=0}^{n-1} {(-1)^{i}C_n^{i} A_{n-i}} ]

需要用大整数。

代码

Java代码

代码语言：javascript复制

import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;

public class Main{
	public static void main(String[] argc){
		Scanner cin = new Scanner (new BufferedInputStream(System.in));
		int T = cin.nextInt();
		while(T>0){
			--T;
			int n = cin.nextInt();
			BigInteger a, t, x;
			a = BigInteger.ZERO;
			t = BigInteger.ONE;
			for (int i = 1; i <= n;   i){
				BigInteger b = BigInteger.ONE;
				if (i >= 2){
					t = t.multiply(BigInteger.valueOf(n-i 1));
					t = t.divide(BigInteger.valueOf(i-1));
				}
				x = cin.nextBigInteger();
				b = b.multiply(t);
				b = b.multiply(x);
				if (1 == (n - i) % 2) a = a.subtract(b);
				else a = a.add(b);
			}
			System.out.println(a);
		}
	}
}

C 代码

代码语言：javascript复制

#include <cstdio>
#include <cstring>
using namespace std;
#define N 3005
#define base 10000
struct Big{
	int d[1000];
	int k,l;
	Big(){l=k=0;}
	Big(int d){input(d);}
	void input(int n){
		memset(d,0,sizeof d);
		k=0;
		if(n==0) l=1;
		else for(l=0;n;n/=base)d[l  ]=n�se;
	}
	void output()const{
		if(k&&l&&d[l-1])printf("-");
		printf("%d",d[l-1]);
		for(int i=l-2;i>=0;i--)printf("d",d[i]);
	}
	bool operator <(const Big &b)const{
		int i=l-1,j=b.l-1;
		if(i!=j)return i<j;
		while(i>=0&&d[i]==b.d[j]){i--;j--;}
		return d[i]<b.d[j];
	}
	Big operator * (const Big &b)const{
		Big c;
		memset(c.d,0,sizeof c.d);
		for(int i=0;i<l;i  )
			for(int j=0;j<b.l;j  ){
				c.d[i j] =d[i]*b.d[j];
				if(c.d[i j]>=base){
					c.d[i j 1] =c.d[i j]/base;
					c.d[i j]%=base;
				}
			}
		c.l=l b.l;
		if(c.l>1&&!c.d[c.l-1])c.l--;
		return c;
	}
	Big operator * (int b)const{
		Big c;
		c.input(b);
		return *this*c;
	}
	Big operator / (int b)const{
		Big c;
		int i,k=0;
		c.l=l;
		for(i=l-1;i>=0;i--){
			c.d[i]=(k d[i])/b;
			k=(k d[i])%b*base;
		}
		while(c.l>1&&!c.d[c.l-1])c.l--;
		return c;
	}
	Big operator   (const Big &b)const{
		Big c=*this;
		int k=0;
		for(int i=0;i<b.l||i<l;i  ){
			if(i<b.l)c.d[i] =b.d[i];
			c.d[i] =k;
			k=0;
			if(c.d[i]>=base){
				c.d[i]-=base;
				k=1;
			}
		}
		if(b.l>l)c.l=b.l;
		if(k)c.d[c.l  ]=1;
		return c;
	}
	Big operator - (const Big &b)const{
		Big c=*this;
		for(int i=0;i<b.l;i  ){
			c.d[i]-=b.d[i];
			if(c.d[i]<0){
				c.d[i] =base;
				c.d[i 1]--;
			}
		}
		while(c.l>1&&!c.d[c.l-1])c.l--;
		return c;
	}
}a[N];
int T,n;
void add(Big &a,Big b){
	if(a.k^b.k){
		if(b<a) a=a-b;
		else a=b-a,a.k=b.k;
	}else a=a b;
}
void sub(Big &a,Big b){
	if(a.k^b.k) a=a b;
	else if(b<a) a=a-b;
	else a=b-a,a.k^=1;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1,d;i<=n;i  ){
			scanf("%d",&d);
			a[i].input(d);
		}
		Big c(1);
		int k=n%2;
		Big ans=a[1];
		if(!k)ans.k=1;
		for(int i=1;i<n;i  ){
			c=c*(n-i)/i;
			k^=1;
			Big t=c*a[i 1];
			if(k) add(ans,t);
			else sub(ans,t);
		}
		ans.output();
		puts("");
	}
}