首个c++代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 高精度整数
struct BigInt {
vector<int> digits;

BigInt() {}
BigInt(int n) {
    if (n == 0) digits.push_back(0);
    else {
        while (n) {
            digits.push_back(n % 10);
            n /= 10;
        }
    }
}

BigInt(const string& s) {
    for (int i = s.size() - 1; i >= 0; i--)
        digits.push_back(s[i] - '0');
}

BigInt& operator=(int n) {
    digits.clear();
    if (n == 0) digits.push_back(0);
    else {
        while (n) {
            digits.push_back(n % 10);
            n /= 10;
        }
    }
    return *this;
}

BigInt operator+(const BigInt& other) const {
    BigInt res;
    int carry = 0;
    int len = max(digits.size(), other.digits.size());
    for (int i = 0; i < len || carry; i++) {
        int sum = carry;
        if (i < digits.size()) sum += digits[i];
        if (i < other.digits.size()) sum += other.digits[i];
        res.digits.push_back(sum % 10);
        carry = sum / 10;
    }
    return res;
}

BigInt operator-(const BigInt& other) const {
    BigInt res;
    int borrow = 0;
    for (int i = 0; i < digits.size(); i++) {
        int sub = digits[i] - borrow;
        if (i < other.digits.size()) sub -= other.digits[i];
        if (sub < 0) {
            sub += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.digits.push_back(sub);
    }
    while (res.digits.size() > 1 && res.digits.back() == 0)
        res.digits.pop_back();
    return res;
}

BigInt operator*(int n) const {
    BigInt res;
    int carry = 0;
    for (int i = 0; i < digits.size() || carry; i++) {
        if (i < digits.size()) carry += digits[i] * n;
        res.digits.push_back(carry % 10);
        carry /= 10;
    }
    return res;
}

string toString() const {
    string s;
    for (int i = digits.size() - 1; i >= 0; i--)
        s += char(digits[i] + '0');
    return s;
}

};

int main() {
int n;
cin >> n;

if (n == 1) {
    cout << 1 << endl;
    return 0;
}
if (n == 2) {
    cout << 5 << endl;
    return 0;
}

// f(n) = 3*f(n-1) - f(n-2) + 2
BigInt f1 = 1;  // f(1)
BigInt f2 = 5;  // f(2)
BigInt fn;

for (int i = 3; i <= n; i++) {
    fn = f2 * 3 - f1 + 2;
    f1 = f2;
    f2 = fn;
}

cout << fn.toString() << endl;

return 0;

}