Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Abel分部求和

Posted by ZxyElf at 2013-06-14 14:35:58 on Problem 1707
...rt


#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;


typedef long long ll;



ll gcd(ll  m,ll n){
	ll r;
	m=abs(m),n=abs(n);
	while (n){
		r=m%n;m=n,n=r;
	}
	return m;
}  

ll lcm(ll m,ll n){
	m=abs(m),n=abs(n);
	return abs(m*n)/gcd(m,n);
}

struct fraction{
	ll a,b;
	fraction(){a=0,b=1;}
	fraction(ll _a,ll _b):a(_a),b(_b){
		ll h=gcd(a,b);
		a/=h,b/=h;
		if (b<0) a=-a,b=-b;
	}
	fraction(ll s){
		a=s;b=1;
	}
}C[21][25];

fraction operator+(const fraction &a,const fraction &b){
	return fraction(a.a*b.b+a.b*b.a,a.b*b.b);
}

fraction operator-(const fraction &a){     
	return fraction(-a.a,a.b);
}

fraction operator-(const fraction &a,const fraction &b){
	return a+(-b);
}

fraction operator*(const fraction &a,const fraction &b){
	return fraction(a.a*b.a,a.b*b.b);
}

fraction operator /(const fraction &a,const fraction &b){
	return fraction(a.a*b.b,a.b*b.a);
}


int main()
{
	int k;cin>>k;
	int i,j,l;
	C[0][1]=1;
	for (i=1;i<=k;i++){
		for (j=1;j<=i;j++){
			C[i][j]=C[i][j]+C[i-1][j];
			C[i][j+1]=C[i][j+1]+C[i-1][j];
		}			
		fraction c0=1+C[i-1][i];
		for (j=1;j<i;j++){
			for (l=1;l<=j+1;l++){
				C[i][l]=C[i][l]-C[j][l]*C[i-1][j];
			}
		}
		for (j=1;j<=i+1;j++)C[i][j]=C[i][j]/c0;
	}
	ll M=1;
	for (i=1;i<=k+1;i++){
		M=lcm(M,C[k][i].b);
	}
	cout<<M;
	for (i=k+1;i>=0;i--){
		cout<<" "<<(C[k][i]*M).a;
	}
	cout<<endl;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator