Submission

Score: 100

User: Dormon

Problemset: อนุกรม

Language: cpp

Time: 0.002 second

Submitted On: 2025-07-04 00:03:28

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

class big_num {
private:
    string plus(const string &lhs, const string &rhs){
        int i = lhs.size() - 1, j = rhs.size() - 1, carry = 0; string ans = "";
        while (i >= 0 || j >= 0 || carry){
            int sum = ((i >= 0)? lhs[i--]-'0':0) + ((j >= 0)? rhs[j--]-'0':0) + carry;
            ans += (sum % 10) + '0', carry = sum / 10;
        }
        reverse(ans.begin(), ans.end()); return ans;
    }
    string minus(const string &lhs, const string &rhs){ // lhs >= rhs
        int i = lhs.size() - 1, j = rhs.size() - 1, borrow = 0; string ans = "";
        while (i >= 0){
            int x = lhs[i--] - '0' - borrow, y = (j >= 0 ? rhs[j--] - '0' : 0);
            if (x < y) x += 10, borrow = 1;
            else borrow = 0;
            ans += (x - y) + '0';
        }
        while (ans.size() > 1 && ans.back() == '0') ans.pop_back();
        reverse(ans.begin(), ans.end()); return ans;
    }
    string mul(const string &lhs, const string &rhs){ // can use fft for O(n log n)
        int n = lhs.size(), m = rhs.size(); vector<int> v(n + m, 0);
        for (int i = n - 1;i >= 0;i--) for (int j = m - 1;j >= 0;j--){
            int mul = (lhs[i] - '0') * (rhs[j] - '0'), sum = v[i + j + 1] + mul;
            v[i + j + 1] = sum % 10, v[i + j] += sum / 10;
        }
        string ans = ""; for (auto x:v) if (!ans.empty() || x) ans += x + '0';
        return ans.empty()?"0":ans;
    }
    string div(const string &lhs, const string &rhs){
        string ans = "", cur = "";
        for (char c:lhs){
            cur += c;
            while (cur.size() > 1 && cur[0] == '0') cur.erase(cur.begin());
            int cnt = 0;
            while (cur.size() > rhs.size() || (cur.size() == rhs.size() && cur >= rhs)) cur = minus(cur, rhs), cnt++;
            ans += cnt + '0';
        }
        while (ans.size() > 1 && ans[0] == '0') ans.erase(ans.begin());
        return ans.empty()?"0":ans;
    }
    string mod(const string &lhs, const string &rhs){
        string cur = "";
        for (char c : lhs){
            cur += c;
            while (cur.size() > 1 && cur[0] == '0') cur.erase(cur.begin());
            while (cur.size() > rhs.size() || (cur.size() == rhs.size() && cur >= rhs)) cur = minus(cur, rhs);
        }
        return cur.empty()?"0":cur;
    }
public:
    string num;
    big_num() : num("0") {}
    big_num(string s){
        num = s;
        while (num.size() > 1 && num[0] == '0') num.erase(num.begin());
    }
    big_num(int s) : big_num(to_string(s)) {}
    big_num(long long s) : big_num(to_string(s)) {}
    
    big_num &operator += (const big_num &rhs){num = plus(num, rhs.num); return *this;}
    big_num &operator -= (const big_num &rhs){num = minus(num, rhs.num); return *this;}
    big_num &operator *= (const big_num &rhs){num = mul(num, rhs.num); return *this;}
    big_num &operator /= (const big_num &rhs){num = div(num, rhs.num); return *this;}
    big_num &operator %= (const big_num &rhs){num = mod(num, rhs.num); return *this;}
    friend big_num operator + (big_num lhs, const big_num &rhs){return lhs += rhs;}
    friend big_num operator - (big_num lhs, const big_num &rhs){return lhs -= rhs;}
    friend big_num operator * (big_num lhs, const big_num &rhs){return lhs *= rhs;}
    friend big_num operator / (big_num lhs, const big_num &rhs){return lhs /= rhs;}
    friend big_num operator % (big_num lhs, const big_num &rhs){return lhs %= rhs;}
    friend istream &operator >> (istream &in, big_num &o){string s; in >> s;o.num = s; return in;}
    friend ostream &operator << (ostream &out, const big_num &o){out << o.num; return out;}
    friend bool operator == (const big_num &lhs, const big_num &rhs){return lhs.num == rhs.num;}
    friend bool operator != (const big_num &lhs, const big_num &rhs){return lhs.num != rhs.num;}
    friend bool operator < (const big_num &lhs, const big_num &rhs){return lhs.num < rhs.num;}
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    if (n == 0){
        cout << "0\n";
        return 0;
    }
    big_num a("0"), b("1"), c("1");
    for (int i = 2;i <= n;i++){
        c = a + b;
        a = b;
        b = c;
    }
    cout << c << '\n';
}