1 //  2 //  main.cpp  3 //  1601  4 //  5 //  Created by wanghan on 16/10/12.  6 //  Copyright © 2016年 wanghan. All rights reserved.  7 //  8   9 #include<cstdio> 10 #include<cstring> 11 #include<vector> 12 #include<iostream> 13 #include<set> 14 #include<map> 15 #include<cassert> 16 using namespace std; 17  18 using namespace std; 19  20 struct BigInteger { 21     typedef unsigned long long LL; 22      23     static const int BASE = 100000000; 24     static const int WIDTH = 8; 25     vector<int> s; 26      27     BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;} 28     BigInteger(LL num = 0) {*this = num;} 29     BigInteger(string s) {*this = s;} 30     BigInteger& operator = (long long num) { 31         s.clear(); 32         do { 33             s.push_back(num % BASE); 34             num /= BASE; 35         } while (num > 0); 36         return *this; 37     } 38     BigInteger& operator = (const string& str) { 39         s.clear(); 40         int x, len = (str.length() - 1) / WIDTH + 1; 41         for (int i = 0; i < len; i++) { 42             int end = str.length() - i*WIDTH; 43             int start = max(0, end - WIDTH); 44             sscanf(str.substr(start,end-start).c_str(), "%d", &x); 45             s.push_back(x); 46         } 47         return (*this).clean(); 48     } 49      50     BigInteger operator + (const BigInteger& b) const { 51         BigInteger c; c.s.clear(); 52         for (int i = 0, g = 0; ; i++) { 53             if (g == 0 && i >= s.size() && i >= b.s.size()) break; 54             int x = g; 55             if (i < s.size()) x += s[i]; 56             if (i < b.s.size()) x += b.s[i]; 57             c.s.push_back(x % BASE); 58             g = x / BASE; 59         } 60         return c; 61     } 62     BigInteger operator - (const BigInteger& b) const { 63         assert(b <= *this); // 减数不能大于被减数 64         BigInteger c; c.s.clear(); 65         for (int i = 0, g = 0; ; i++) { 66             if (g == 0 && i >= s.size() && i >= b.s.size()) break; 67             int x = s[i] + g; 68             if (i < b.s.size()) x -= b.s[i]; 69             if (x < 0) {g = -1; x += BASE;} else g = 0; 70             c.s.push_back(x); 71         } 72         return c.clean(); 73     } 74     BigInteger operator * (const BigInteger& b) const { 75         int i, j; LL g; 76         vector<LL> v(s.size()+b.s.size(), 0); 77         BigInteger c; c.s.clear(); 78         for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j]; 79         for (i = 0, g = 0; ; i++) { 80             if (g ==0 && i >= v.size()) break; 81             LL x = v[i] + g; 82             c.s.push_back(x % BASE); 83             g = x / BASE; 84         } 85         return c.clean(); 86     } 87     BigInteger operator / (const BigInteger& b) const { 88         assert(b > 0);  // 除数必须大于0 89         BigInteger c = *this;       // 商:主要是让c.s和(*this).s的vector一样大 90         BigInteger m;               // 余数:初始化为0 91         for (int i = s.size()-1; i >= 0; i--) { 92             m = m*BASE + s[i]; 93             c.s[i] = bsearch(b, m); 94             m -= b*c.s[i]; 95         } 96         return c.clean(); 97     } 98     BigInteger operator % (const BigInteger& b) const { //方法与除法相同 99         BigInteger c = *this;100         BigInteger m;101         for (int i = s.size()-1; i >= 0; i--) {102             m = m*BASE + s[i];103             c.s[i] = bsearch(b, m);104             m -= b*c.s[i];105         }106         return m;107     }108     // 二分法找出满足bx<=m的最大的x109     int bsearch(const BigInteger& b, const BigInteger& m) const{110         int L = 0, R = BASE-1, x;111         while (1) {112             x = (L+R)>>1;113             if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;}114             else R = x;115         }116     }117     BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}118     BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}119     BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}120     BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}121     BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}122     123     bool operator < (const BigInteger& b) const {124         if (s.size() != b.s.size()) return s.size() < b.s.size();125         for (int i = s.size()-1; i >= 0; i--)126             if (s[i] != b.s[i]) return s[i] < b.s[i];127         return false;128     }129     bool operator >(const BigInteger& b) const{return b < *this;}130     bool operator<=(const BigInteger& b) const{return !(b < *this);}131     bool operator>=(const BigInteger& b) const{return !(*this < b);}132     bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}133     bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}134 };135 136 ostream& operator << (ostream& out, const BigInteger& x) {137     out << x.s.back();138     for (int i = x.s.size()-2; i >= 0; i--) {139         char buf[20];140         sprintf(buf, "%08d", x.s[i]);141         for (int j = 0; j < strlen(buf); j++) out << buf[j];142     }143     return out;144 }145 146 istream& operator >> (istream& in, BigInteger& x) {147     string s;148     if (!(in >> s)) return in;149     x = s;150     return in;151 }152 set<BigInteger> s;153 map<BigInteger, int> m;154 155 int main() {156     BigInteger dp[5050];157     int n;158     while(cin>>n)159     {160         for(int i=0;i<5050;++i)161             dp[i]=BigInteger(0);162         dp[1]=BigInteger(1);163         dp[2]=BigInteger(2);164         if(n<=2){165             cout<<dp[n]<<endl;166             continue;167         }168         for(int i=3;i<=n;i++)169             dp[i]=dp[i-1]+dp[i-2];170         cout<<dp[n]<<endl;171     }172     return 0;173 }