简单大数
(要压位,不然会超内存)
#include#include #include #include #include using namespace std;const int base = 1000000;struct BigInt{ vector Num; BigInt() { Num.clear(); } void Set(int n) { Num.clear(); Num.push_back(n); } BigInt operator + (const BigInt &a) const { BigInt c; int len1 = Num.size(), len2 = a.Num.size(); int i; for(i = 0; i < len1 && i < len2; ++i) c.Num.push_back(Num[i] + a.Num[i]); for(; i < len1; ++i) c.Num.push_back(Num[i]); for(; i < len2; ++i) c.Num.push_back(a.Num[i]); for(int i = 0; i < c.Num.size(); ++i) { if(c.Num[i] >= base) { if(i == c.Num.size() - 1) c.Num.push_back(c.Num[i] / base); else c.Num[i+1] += c.Num[i] / base; c.Num[i] %= base; } } return c; } void Print() { int len = Num.size(); printf("%d",Num[len-1]); for(int i = len - 2; i >= 0; --i) { int k = base / 10; while(Num[i] < k) { printf("0"); k /= 10; } printf("%d",Num[i]); } printf("\n"); }}N[500000];void Init(){ N[1].Set(1);N[2].Set(1); N[3].Set(1);N[4].Set(1); for(int i = 5; ; ++i) { N[i] = N[i-1] + N[i-2] + N[i-3] + N[i-4]; if(N[i].Num.size() * 5 > 2005) break; }}int main(){ Init(); int n; while(cin >> n) { N[n].Print(); } return 0;}