_zhuchenzhang_ @ 2018-08-05 17:17:00
#include <bits/stdc++.h>
using namespace std;
template <typename _Tp>
inline _Tp Max(_Tp a,_Tp b)
{
return a>b?a:b;
}
template <typename _Tp>
inline _Tp Min(_Tp a,_Tp b)
{
return a<b?a:b;
}
struct BN
{
#define LEN_SIZE 10001
private:
/********************************************************/// user member
int len;
int a[LEN_SIZE];
bool is_nn;//is negative number
public:
inline BN UnAbs(BN X)
{
X.is_nn=true;
return X;
}
inline BN Abs(BN X)
{
X.is_nn=false;
return X;
}
inline void clear() { is_nn=false , memset(a,0,sizeof a) , len=0 ; return; }
inline void BN_read()
{
char t=getchar();
clear();
for(;!isdigit(t);t=getchar()) if(t=='-') is_nn=true;
for(;isdigit(t);t=getchar()) a[++len]=(t-'0');
return;
}
inline void BN_write()
{
if(is_nn) putchar('-');
for(int i=1;i<=len;++i) putchar(a[i]+'0');
return;
}
template <typename _int>
inline void change(_int A)
{
clear();
if(!A)
{
len=1;
a[1]=0;
is_nn=false;
return;
}
_int _A=A;
if(_A<0) _A=-_A,is_nn=true;
for(;_A;++len,_A/=10);
_A=A;
if(is_nn) _A=-_A;
for(int i=len;i;--i) a[i]=_A%10,_A/=10;
return;
}
BN operator = (const BN &next)
{
clear();
is_nn=next.is_nn;
len=next.len;
for(int i=1;i<=next.len;++i) a[i]=next.a[i];
return *this;
}
BN operator + (const BN &next)
{
if(!next) return *this;
if(!(*this)) return next;
BN temp;
temp.clear();
if((next.is_nn&&is_nn)||(!next.is_nn&&!is_nn))
{
if(is_nn) temp.is_nn=true;
BN A,B;
A.clear(),B.clear();
A.len=len,B.len=next.len;
int Len=Max(len,next.len),_len=Min(len,next.len),LEN;
for(int i=1,I=A.len;i<=A.len&&I;++i,--I) A.a[I]=a[i];
for(int i=1,I=B.len;i<=B.len&&I;++i,--I) B.a[I]=next.a[i];
for(int i=1;i<=_len;++i)
{
A.a[i]+=B.a[i];
if(A.a[i]>=10) A.a[i]-=10,A.a[i+1]++;
}
for(int i=_len+1;i<=Len;++i)
{
if(A.len<B.len) A.a[i]+=B.a[i];
if(A.a[i]>=10) A.a[i]-=10,A.a[i+1]++;
}
for(LEN=LEN_SIZE;!A.a[LEN];--LEN);
temp.len=LEN;
for(int i=LEN,I=1;I<=LEN&&i;++I,--i) temp.a[i]=A.a[I];
return temp;
}
else;
}
#undef LEN_SIZE
};
int main()
{
BN A[5001];
int n;
scanf("%d",&n);
A[0].change(0),A[1].change(1),A[2].change(2);
for(int i=3;i<=n;++i) A[i]=A[i-1]+A[i-2];
A[n].BN_write();
return 0;
}
求助大佬,没超时又爆内存
by Marser @ 2018-08-05 17:18:15
BN定义成全局变量
by _zhuchenzhang_ @ 2018-08-05 17:18:33
精简了一部分代码,放不下了。提交记录
by Marser @ 2018-08-05 17:18:56
5000*10000还想不爆内存?
by _zhuchenzhang_ @ 2018-08-05 17:18:59
@Marser 我试试
by _zhuchenzhang_ @ 2018-08-05 17:20:48
@Marser 貌似再一次MLE 记录
by _zhuchenzhang_ @ 2018-08-05 17:21:38
@Marser 好吧没算内存。。。(傻到忘记算内存)
by _zhuchenzhang_ @ 2018-08-05 17:24:04
@Marser 谢谢,过了
by Marser @ 2018-08-05 17:24:34
@zhuchenzhang 不用谢
by 不到前10不改名 @ 2018-08-05 17:45:36
@Marser 我记得100000000都没mle啊!