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;
}