题解 | 小红的二叉树

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

// 非根且非叶节点数量*3 + 有子节点的根节点
// 2^n n <=1e4 数字巨大，int明显越界，需要提前mod
// (ab)%m = (a%m*b%m)%m
// (a+b)%m = (a%m+b%m)%m
// (a^n)%m = ((a%m)*(a^(n-1))%m)%m

int main() {
    int n;
    cin >> n;
    //(2^(n-1)-2)*3+1
    int64_t cnt = 0;
    if(n > 1) {
        int bits = 30;
        auto s = (n - 1) / bits;
        auto l = (n - 1) % bits;
        int64_t t = 1;
        int64_t mod = 1e9+7;
        int64_t v = int64_t(2) << s;
        for(auto i = 0; i < s; i++) {
            t <<= bits;
            t %= mod;
        }
        t <<= l;
        t %= mod;
        cnt = (t - 2)*3;
        if(n >= 2) {
            cnt += 1;
        }
        cnt %= mod;
    }
    cout << cnt << endl;

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