题解 | 小红的二叉树

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

int main() {
    constexpr int MOD = 1e9+7;
    int n; cin >> n;
    vector<int> dp;
    dp.reserve(n + 1);
    dp.push_back(0);
    dp.push_back(0);
    dp.push_back(1);

    if (n <= 2) {
        cout << dp[n];
    } else {
        --n;
        while (--n) {
            dp.push_back((dp.back() * 2 + 5) % MOD);
        }
        cout << dp.back();
    }


}
// 64 位输出请用 printf("%lld")