| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Abel分部求和...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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator