| ||||||||||
| 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 | |||||||||
ACAC/*
username:40962501
*/
#include<iostream>
#include<stdio.h>
using namespace std;
const int BASE=1000000000;
const int MAXD=8592;
struct BigPosInt{
__int64 d[MAXD];
int n;
};
void InitBpi(BigPosInt &bpi);
void PrintBpi(BigPosInt &bpi);
void Inc(BigPosInt &bpi);
void Dec(BigPosInt &bpi);
void Multiply(const BigPosInt &bpi1,const BigPosInt &bpi2, BigPosInt &bpi3);
int main(){
int N;
BigPosInt ans;
BigPosInt bpi1,bpi2;
int i;
scanf("%d",&N);
printf("2\n");N--;
InitBpi(bpi1);
bpi1.d[0]=2;bpi1.n=1;
while(N-->0){
InitBpi(ans);
bpi2.n=bpi1.n;
for(int i=0;i<bpi1.n;i++){
bpi2.d[i]=bpi1.d[i];
}
Dec(bpi2);Multiply(bpi1,bpi2,ans);
Inc(ans);
PrintBpi(ans);
bpi1.n=ans.n;
for(int i=0;i<ans.n;i++){
bpi1.d[i]=ans.d[i];
}
}
return 0;
}
void InitBpi(BigPosInt &bpi){
for(int i=0;i<MAXD;i++){
bpi.d[i]=0;
}
bpi.n=0;
}
void PrintBpi(BigPosInt &bpi){
if(bpi.n<=0) return ;
int i;
printf("%I64d",bpi.d[bpi.n-1]);
for(i=bpi.n-2;i>=0;i--){
if(bpi.d[i]<100000000){
printf("%.9I64d",bpi.d[i]);
}
else {
printf("%I64d",bpi.d[i]);
}
}
printf("\n");
}
void Inc(BigPosInt &bpi){
int i;
bpi.d[0]++;
for(i=0;i<bpi.n;i++){
if(bpi.d[i]>=BASE){
bpi.d[i]-=BASE;
bpi.d[i+1]++;
}
else break;
}
if(bpi.d[bpi.n]!=0){
bpi.n++;
}
}
void Dec(BigPosInt &bpi){
int i;
bpi.d[0]--;
for(i=0;i<bpi.n;i++){
if(bpi.d[i]<0){
bpi.d[i]+=BASE;
bpi.d[i+1]--;
}
else break;
}
if(bpi.d[bpi.n-1]==0){
bpi.n--;
}
}
void Multiply(const BigPosInt &bpi1,const BigPosInt &bpi2, BigPosInt &bpi3){
int i,j;
InitBpi(bpi3);
for(i=0;i<bpi1.n;i++){
for(j=0;j<bpi2.n;j++){
bpi3.d[i+j]+=bpi1.d[i]*bpi2.d[j];
bpi3.d[i+j+1]+=bpi3.d[i+j]/BASE;
bpi3.d[i+j]%=BASE;
}
}
for(i=bpi1.n+bpi2.n+10;i>=0;i--){
if(bpi3.d[i]!=0){
bpi3.n=i+1;
break;
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator